c語言設計迷宮
A. 走迷宮的c語言版代碼求助 程序開始運行時顯示一個迷宮地圖，迷宮中央有一隻老鼠，迷宮的右下方有一個糧
/*註：本程序探索迷宮的優先順序=> 1-下、2-右、3-上、4-左 <=總體趨勢：下右，逆時針方向。因為出口就在右邊下方*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define stack_init_size 200
#define stack_increment 10
#define OVERFLOW 0
#define OK 1
#define ERROE 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef struct{
int x;
int y;
}PosType;
typedef struct {
int ord; // 通道塊在路徑上的"序號"
PosType seat; //通道塊在迷宮中的"坐標位置"
int di; //從此通道塊走向下一通道塊的"方向"
}SElemType;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
int mg[20][20];
/*隨機生成迷宮的函數
/*為了能夠讓盡量能通過，將能通過的塊和不能通過的塊數量比大致為2:1*/
void Random(){
int i,j,k;
srand(time(NULL));
mg[1][0]=mg[1][1]=mg[18][19]=0; //將入口、出口設置為"0"即可通過
for(j=0;j<20;j++)
mg[0][j]=mg[19][j]=1; /*設置迷宮外圍"不可走"，保證只有一個出口和入口*/
for(i=2;i<19;i++)
mg[i][0]=mg[i-1][19]=1; /*設置迷宮外圍"不可走"，保證只有一個出口和入口*/
for(i=1;i<19;i++)
for(j=1;j<19;j++){
k=rand()%3; //隨機生成0、1、2三個數
if(k)
mg[i][j]=0;
else{
if((i==1&&j==1)||(i==18&&j==18)) /*因為距入口或出口一步的路是必經之路，故設該通道塊為"0"加大迷宮能通行的概率*/
mg[i][j]=0;
else
mg[i][j]=1;
}
}
}
//構造一個空棧
Status InitStack(SqStack &s){
s.base =(SElemType *)malloc(stack_init_size * sizeof(SElemType));
if(!s.base) return OVERFLOW;
s.top=s.base;
s.stacksize=stack_init_size;
return OK;
}
//當前塊可否通過
Status Pass(PosType e){
if (mg[e.x][e.y]==0) //0時可以通過
return OK; // 如果當前位置是可以通過，返回1
return OVERFLOW; // 其它情況返回0
}
//留下通過的足跡
Status FootPrint(PosType e){
mg[e.x][e.y]=7;
return OK;
}
//壓入棧
Status Push(SqStack &s,SElemType e){
if(s.top-s.base>=s.stacksize){
s.base=(SElemType *)realloc(s.base,(s.stacksize+stack_increment) *sizeof(SElemType));
if(!s.base)exit(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=stack_increment;
}
*s.top++=e;
return OK;
}
//出棧
Status Pop(SqStack &s,SElemType &e){
if(s.top==s.base)
return ERROE;
e=*--s.top;
return OK;
}
//下一步
PosType NextPos(PosType &e,int dir){
PosType E;
switch(dir){
case 1:E.x=e.x; //向下
E.y=e.y+1;
break;
case 2:E.x=e.x+1; //向右
E.y=e.y;
break;
case 3:E.x=e.x; //向上
E.y=e.y-1;
break;
case 4:E.x=e.x-1; //向左
E.y=e.y;
break;
}
return E;
}
//是否空棧
Status StackEmpty(SqStack s){
if (s.top==s.base)
return OK;
return OVERFLOW;
}
//留下不能通過的足跡
Status MarkPrint(PosType e){
mg[e.x][e.y]=3;
return OK;
}
//迷宮函數
// 若迷宮maze中從入口 start到出口 end的通道，則求得一條存放在棧中
// （從棧底到棧頂），並返回TRUE；否則返回FALSE
Status MazePath(int mg,PosType start,PosType end,SqStack &s){
PosType curpos;
InitStack(s);
SElemType e;
int curstep;
curpos=start; // 設定"當前位置"為"入口位置"
curstep=1; // 探索第一步
do{
if(Pass(curpos)){ // 當前位置可通過，即是未曾走到過的通道塊
FootPrint(curpos); // 留下足跡
e.di =1;
e.ord = curstep;
e.seat= curpos;
Push(s,e); // 加入路徑
if(curpos.x==end.x&&curpos.y==end.y){
printf("\n\n0∩_∩0 能到達終點!");
return TRUE;
}
curpos=NextPos(curpos,1); // 下一位置是當前位置的東鄰
curstep++; // 探索下一步
}
else{ // 當前位置不能通過
if(!StackEmpty(s)){
Pop(s,e);
while(e.di==4&&!StackEmpty(s)){
MarkPrint(e.seat);
Pop(s,e);
}
if(e.di<4){
e.di++;
Push(s,e); // 留下不能通過的標記，並退回一步
curpos=NextPos(e.seat,e.di); /* 當前位置設為新方向的相鄰塊*/
}//if
}//if
}//else
}while(!StackEmpty(s));
printf("\n\n囧 ! 不能到達終點!");
return FALSE;
}
//列印迷宮
void PrintMaze(){
int i,j;
printf("運行路徑:\n\n");
for(i=0;i<20;i++){
for(j=0;j<20;j++){
if(mg[i][j]==0)printf(" ");
else if(mg[i][j]==1) printf("■"); //迷宮的"牆"
else if(mg[i][j]==3) printf("◇"); //不通的路
else if(mg[i][j]==7)printf("○"); //通過的路徑
}
printf("\n");
}
printf("\n");
}
void main(){
SqStack S;
PosType start,end;
start.x=1;start.y=0; //起點坐標
end.x=18;end.y=19; //終點坐標
printf("\n==================迷宮游戲==================");
printf("\n說明:■不能走的區域\t◇走不通的區域");
printf("\n '空格'代表未到過的區域");
printf("\n ○代表能通過的路徑，指向終點");
printf("\n============================================");
Random();
printf("\n\nTest 1:");
MazePath(mg[20][20],start,end,S);
PrintMaze();
system("pause");
Random();
printf("\nTest 2:");
MazePath(mg[20][20],start,end,S);
PrintMaze();
system("pause");
Random();
printf("\nTest 3:");
MazePath(mg[20][20],start,end,S);
PrintMaze();
printf("\n==========程序退出，感謝使用!==========\n");
}
B. c語言的迷宮問題
//尋路_帶權重_帶障礙_最短_文件地圖_不閃------wlfryq------//
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<windows.h>
typedefstruct
{
intx;
inty;
}_PT;
_PTpt;
introw=0,col=0;
//設置CMD窗口游標位置
voidsetxy(intx,inty)
{
COORDcoord={x,y};
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),coord);
}
//獲取當前CMD當前游標所在位置
voidgetxy()
{
HANDLEhConsole=GetStdHandle(STD_OUTPUT_HANDLE);
COORDcoordScreen={0,0};//游標位置
CONSOLE_SCREEN_BUFFER_INFOcsbi;
if(GetConsoleScreenBufferInfo(hConsole,&csbi))
{
pt.x=csbi.dwCursorPosition.X;
pt.y=csbi.dwCursorPosition.Y;
}
}
typedefstruct
{
intx;
inty;
inttype;
intv;
}PT;
PT**s=NULL,stack[50],start,end,c;
intpos=0;
voidprt()
{
inti,j;
system("cls");
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
if(s[i][j].type==1)
{
printf("■");
}
elseif(i==end.x&&j==end.y)
{
printf("★");
}
elseif(i==c.x&&j==c.y)
{
printf("◎");
}
else
{
printf("");
}
}
printf(" ");
}
Sleep(500);
}
voidstack_in(PTa)
{
stack[pos++]=a;
}
PTstack_out()
{
inti;
PTt;
t=stack[0];
for(i=0;i<pos-1;i++)
{
stack[i]=stack[i+1];
}
pos--;
returnt;
}
voidfun()
{
PTa;
intx,y,v;
while(1)
{
if(pos==0)
{
break;
}
a=stack_out();
x=a.x;
y=a.y;
if(x==start.x&&y==start.y)
{
break;
}
v=s[x][y].v;
if(x-1>=0&&s[x-1][y].type==0&&(s[x-1][y].v==-1||s[x-1][y].v>v+1))
{
s[x-1][y].v=v+1;
stack_in(s[x-1][y]);
}
if(x+1<=row-1&&s[x+1][y].type==0&&(s[x+1][y].v==-1||s[x-1][y].v>v+1))
{
s[x+1][y].v=v+1;
stack_in(s[x+1][y]);
}
if(y-1>=0&&s[x][y-1].type==0&&(s[x][y-1].v==-1||s[x-1][y].v>v+1))
{
s[x][y-1].v=v+1;
stack_in(s[x][y-1]);
}
if(y+1<=col-1&&s[x][y+1].type==0&&(s[x][y+1].v==-1||s[x-1][y].v>v+1))
{
s[x][y+1].v=v+1;
stack_in(s[x][y+1]);
}
}
}
voidgo(intx,inty)
{
printf(" 按任意鍵開始 ");
getchar();
intv;
while(1)
{
if(x==end.x&&y==end.y)
{
setxy(0,y+2);
printf("end....");
return;
}
v=s[x][y].v;
if(v==0)
{
return;
}
if(x-1>=0&&s[x-1][y].v==v-1)
{
c=s[x-1][y];
setxy(y*2,x);
x=x-1;
printf("");
setxy(y*2,x);
printf("◎");
Sleep(500);
continue;
}
elseif(x+1<=row-1&&s[x+1][y].v==v-1)
{
c=s[x+1][y];
setxy(y*2,x);
x++;
printf("");
setxy(y*2,x);
printf("◎");
Sleep(500);
continue;
}
elseif(y-1>=0&&s[x][y-1].v==v-1)
{
c=s[x][y-1];
setxy(y*2,x);
y--;
printf("");
setxy(y*2,x);
printf("◎");
Sleep(500);
continue;
}
elseif(y+1<=col-1&&s[x][y+1].v==v-1)
{
c=s[x][y+1];
setxy(y*2,x);
y++;
printf("");
setxy(y*2,x);
printf("◎");
Sleep(500);
continue;
}
}
printf(" returngo ");
system("pause");
}
voidGetMapFromFile()
{
inti,j,x,y,len;
charch[50]={' '};
FILE*fp=fopen("e:\map1.txt","r");
if(fp==NULL)
{
printf("openfilefailed. ");
return;
}
x=0;
while(!feof(fp))
{
fgets(ch,50,fp);
row++;
}
col=strlen(ch);
fseek(fp,0L,SEEK_SET);
while(!feof(fp))
{
fgets(ch,50,fp);
if(s==NULL)
{
len=strlen(ch);
for(i=len-1;i>0;i--)
{
if(ch[i]!='0'&&ch[i]!='1')
{
ch[i]=' ';
}
else
{
break;
}
}
len=strlen(ch);
s=(PT**)malloc(sizeof(PT*)*row);
for(j=0;j<len;j++)
{
*(s+j)=(PT*)malloc(sizeof(PT)*len);
}
}
y=0;
for(i=0;i<len;i++)
{
s[x][y].type=ch[i]-48;
s[x][y].x=x;
s[x][y].y=y;
s[x][y].v=-1;
y++;
}
x++;
}
start=s[row-2][1];
end=s[row-2][len-2];
fclose(fp);
}
intmain()
{
GetMapFromFile();
inti,j;
intx,y;
x=end.x;
y=end.y;
s[x][y].v=0;
stack_in(end);
fun();
c=start;
prt();
go(start.x,start.y);
return0;
}
C. C語言迷宮問題，求該演算法的時間和空間的復雜度。迷宮的路徑已經定義好，求出路的演算法。
該演算法是不穩定的，其時空復雜度不僅和m,n有關，還和mg[][]的具體數值有關。
最壞情況下：每個點都試探過才走到終點。此時時間復雜度為：(m*n-1)*4，（其中4為4個方向），空間復雜度m*n*2，(其中m*n為存儲迷宮圖空間，m*n為棧空間);
再好情況下：一次試探過就走到終點。此時時間復雜度為：(min(m,n)-1)，空間復雜度m*n;
所以：
該演算法時間復雜度為：[(m*n-1)*4+(min(m,n)-1)]/2，約為2×m×n
空間復雜度為3*m*n/2
D. 數據結構與演算法作業：用C語言編程隨機生成一個迷宮，然後找出從入口到出口的路線圖。急！
幾點說明：
1．本程序是動態的，運行後自動尋找迷宮出路
2.本程序對C語言剛學完的有很大的意義．
3.四周是牆,坐標(1,1)是入口,右下腳是出口
聲明:本程序用VC調試是無法通過的需要修改
本程序調試工具是TC.....................
#include "graphics.h"
#include "dos.h"
#include "stdlib.h"
#include "process.h"
#define MAX_COL 14/*定義迷宮大小*/
#define MAX_ROW 14
typedef struct
{ int vert;
int horiz;
}offsets;
mapture(int i,int j,int k);/*標記迷宮，（i,j）標記為k模式*/
initmaze();/*初始化迷宮數組*/
findmaze(int i,int j);/*找到了（i,j）可走，標記*/
mapmaze();/*畫出原始迷宮*/
int findpath(int row,int col);/*遞歸函數，找出迷宮路徑*/
mapbar();/*畫出方格*/
initgrap();/*初始化VGA*/
print();/*迷宮走完後，輸出是否成功 */
int startx=50,starty=50;/*畫圖的屏幕坐標*/
int maze[MAX_ROW][MAX_COL];
offsets move[8]={{0,1},{1,1},{-1,1},{1,0},{-1,0},{0,-1},{1,-1},{-1,-1}}; /*8個方向尋找*/
initmaze()/*初始化迷宮數組 */
{ int i,j;
for(i=0;i<MAX_ROW;i++)/*迷宮四周設置為1 代表牆*/
{ maze[i][0]=1;
maze[i][MAX_COL-1]=1;
}
for(i=0;i<MAX_COL;i++)
{ maze[0][i]=1;
maze[MAX_ROW-1][i]=1;
}
randomize();
for(i=1;i<MAX_ROW-1;i++)/*迷宮圖形隨機產生 1表示不通 0表示可行*/
for(j=1;j<MAX_COL-1;j++)
{
maze[i][j]=random(2);
}
}
findmaze(int i,int j)/*找到 （i,j）可走*/
{
mapture(j,i,2);/*在圖形上標記*/
sleep(1);
}
returnmaze(int i,int j)/*找到（i,j）可走 ，但下一步無路走則標記*/
{
mapture(j,i,3);/*在圖形上標記*/
sleep(1);
}
print(int i)/*迷宮走完後，輸出是否成功*/
{ settextstyle(1,0,5);
if(i==1)
outtextxy(340,400,"Ture path!");
else if(i==2)
outtextxy(340,400,"No path!");
}
int findpath(int row,int col)/*用遞歸法找迷宮*/
{ int direct,next_row,next_col;
direct=0;
maze[1][1]=2;
mapture(1,1,2);
sleep(1);
while(direct<8)/*8個方向尋找*/
{ next_row=row+move[direct].vert;/*設置下一步坐標*/
next_col=col+move[direct].horiz;
if(maze[next_row][next_col]==0) /*可走，便標記*/
{ maze[next_row][next_col]=2;
findmaze(next_row,next_col) ;
if(next_row==(MAX_ROW-2)&&next_col==(MAX_COL-2))/*找到出口退出程序*/
{ print(1);
getch();
exit(0);
}
else
findpath(next_row,next_col);/*沒有到出口繼續遞歸*/
maze[next_row][next_col]=3;
returnmaze(next_row,next_col);
}
direct++;
}
return(row);
}
TC調試良好
E. 誰有C語言，生成隨機迷宮的代碼
#include<stdio.h>
#include<conio.h>
#include<windows.h>
#include<time.h>
#defineHeight31//迷宮的高度，必須為奇數
#defineWidth25//迷宮的寬度，必須為奇數
#defineWall1
#defineRoad0
#defineStart2
#defineEnd3
#defineEsc5
#defineUp1
#defineDown2
#defineLeft3
#defineRight4
intmap[Height+2][Width+2];
voidgotoxy(intx,inty)//移動坐標
{
COORDcoord;
coord.X=x;
coord.Y=y;
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),coord);
}
voidhidden()//隱藏游標
{
HANDLEhOut=GetStdHandle(STD_OUTPUT_HANDLE);
CONSOLE_CURSOR_INFOcci;
GetConsoleCursorInfo(hOut,&cci);
cci.bVisible=0;//賦1為顯示，賦0為隱藏
SetConsoleCursorInfo(hOut,&cci);
}
voidcreate(intx,inty)//隨機生成迷宮
{
intc[4][2]={0,1,1,0,0,-1,-1,0};//四個方向
inti,j,t;
//將方向打亂
for(i=0;i<4;i++)
{
j=rand()%4;
t=c[i][0];c[i][0]=c[j][0];c[j][0]=t;
t=c[i][1];c[i][1]=c[j][1];c[j][1]=t;
}
map[x][y]=Road;
for(i=0;i<4;i++)
if(map[x+2*c[i][0]][y+2*c[i][1]]==Wall)
{
map[x+c[i][0]][y+c[i][1]]=Road;
create(x+2*c[i][0],y+2*c[i][1]);
}
}
intget_key()//接收按鍵
{
charc;
while(c=getch())
{
if(c==27)returnEsc;//Esc
if(c!=-32)continue;
c=getch();
if(c==72)returnUp;//上
if(c==80)returnDown;//下
if(c==75)returnLeft;//左
if(c==77)returnRight;//右
}
return0;
}
voidpaint(intx,inty)//畫迷宮
{
gotoxy(2*y-2,x-1);
switch(map[x][y])
{
caseStart:
printf("入");break;//畫入口
caseEnd:
printf("出");break;//畫出口
caseWall:
printf("※");break;//畫牆
caseRoad:
printf("");break;//畫路
}
}
voidgame()
{
intx=2,y=1;//玩家當前位置，剛開始在入口處
intc;//用來接收按鍵
while(1)
{
gotoxy(2*y-2,x-1);
printf("☆");//畫出玩家當前位置
if(map[x][y]==End)//判斷是否到達出口
{
gotoxy(30,24);
printf("到達終點，按任意鍵結束");
getch();
break;
}
c=get_key();
if(c==Esc)
{
gotoxy(0,24);
break;
}
switch(c)
{
caseUp://向上走
if(map[x-1][y]!=Wall)
{
paint(x,y);
x--;
}
break;
caseDown://向下走
if(map[x+1][y]!=Wall)
{
paint(x,y);
x++;
}
break;
caseLeft://向左走
if(map[x][y-1]!=Wall)
{
paint(x,y);
y--;
}
break;
caseRight://向右走
if(map[x][y+1]!=Wall)
{
paint(x,y);
y++;
}
break;
}
}
}
intmain()
{
inti,j;
srand((unsigned)time(NULL));//初始化隨即種子
hidden();//隱藏游標
for(i=0;i<=Height+1;i++)
for(j=0;j<=Width+1;j++)
if(i==0||i==Height+1||j==0||j==Width+1)//初始化迷宮
map[i][j]=Road;
elsemap[i][j]=Wall;
create(2*(rand()%(Height/2)+1),2*(rand()%(Width/2)+1));//從隨機一個點開始生成迷宮，該點行列都為偶數
for(i=0;i<=Height+1;i++)//邊界處理
{
map[i][0]=Wall;
map[i][Width+1]=Wall;
}
for(j=0;j<=Width+1;j++)//邊界處理
{
map[0][j]=Wall;
map[Height+1][j]=Wall;
}
map[2][1]=Start;//給定入口
map[Height-1][Width]=End;//給定出口
for(i=1;i<=Height;i++)
for(j=1;j<=Width;j++)//畫出迷宮
paint(i,j);
game();//開始游戲
getch();
return0;
}
F. c語言迷宮問題，以一個m×n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。
#defineSTACK_SIZE1000
#defineTRUE1
#defineFALSE0
#include<stdio.h>
shortDIRECTION_UP=1;
shortDIRECTION_RIGHT=1<<1;
shortDIRECTION_DOWN=1<<2;
shortDIRECTION_LEFT=1<<3;
shortALL_DIRECTIONS=DIRECTION_UP|DIRECTION_RIGHT|DIRECTION_DOWN|DIRECTION_LEFT;
typedefstruct{
intx;
inty;
shortdirections;
}Cell;
typedefstruct{
Cellelem[STACK_SIZE];
inttop;
}Stack;
voidinitStack(Stack*s){
s->top=-1;
}
intisEmpty(Stack*s){
return(s->top==-1?TRUE:FALSE);
}
voidpush(Stack*s,Celle){
s->top++;
s->elem[s->top]=e;
}
voidpop(Stack*s,Cell*e){
*e=s->elem[s->top];
s->top--;
}
inthasDirection(Cell*e,shortd){
return(e->directions&d)!=0?1:0;
}
voidremoveDirection(Cell*e,shortd){
e->directions=e->directions&(~d);
}
intmain(){
inti,j;
intm,n;
intentranceX,entranceY,exitX,exitY;
scanf("%d%d",&m,&n);
shorta[m][n];
shortvisited[m][n];
for(i=0;i<m;i++){
for(j=0;j<n;j++){
scanf("%d",&a[i][j]);
visited[i][j]=0;
}
}
scanf("%d%d%d%d",&entranceX,&entranceY,&exitX,&exitY);
Stacksteps;
initStack(&steps);
Celle;
e.y=entranceX;
e.x=entranceY;
e.directions=ALL_DIRECTIONS;
push(&steps,e);
visited[entranceX][entranceY]=1;
while(!isEmpty(&steps)){
pop(&steps,&e);
if(e.x==exitX&&e.y==exitY){
push(&steps,e);
break;
}
if(e.x>0&&hasDirection(&e,DIRECTION_UP)&&a[e.x-1][e.y]==0&&!visited[e.x-1][e.y]){
removeDirection(&e,DIRECTION_UP);
push(&steps,e);
e.x--;
e.directions=ALL_DIRECTIONS;
removeDirection(&e,DIRECTION_DOWN);
push(&steps,e);
visited[e.x][e.y]=1;
}elseif(e.y<n-1&&hasDirection(&e,DIRECTION_RIGHT)&&a[e.x][e.y+1]==0&&!visited[e.x][e.y+1]){
removeDirection(&e,DIRECTION_RIGHT);
push(&steps,e);
e.y++;
e.directions=ALL_DIRECTIONS;
removeDirection(&e,DIRECTION_LEFT);
push(&steps,e);
visited[e.x][e.y]=1;
}elseif(e.x<m-1&&hasDirection(&e,DIRECTION_DOWN)
&&a[e.x+1][e.y]==0&&!visited[e.x+1][e.y]){
removeDirection(&e,DIRECTION_DOWN);
push(&steps,e);
e.x++;
e.directions=ALL_DIRECTIONS;
removeDirection(&e,DIRECTION_UP);
push(&steps,e);
visited[e.x][e.y]=1;
}elseif(e.y>0&&hasDirection(&e,DIRECTION_LEFT)
&&a[e.x][e.y-1]==0&&!visited[e.x][e.y-1]){
removeDirection(&e,DIRECTION_LEFT);
push(&steps,e);
e.y--;
e.directions=ALL_DIRECTIONS;
removeDirection(&e,DIRECTION_RIGHT);
push(&steps,e);
visited[e.x][e.y]=1;
}
}
if(isEmpty(&steps)){
printf("No");
}else{
printf("Yes");
}
return0;
}