註釋非常詳細,希望對妳有所幫助。
#include
#include
#defineM15
#defineN15
structmark//定義迷宮內點的坐標類型
{
intx;
inty;
};
structElement//戀棧元素,嘿嘿。。
{
intx,y;//x行,y列
intd;//d下壹步的方向
};
typedefstructLStack//鏈棧
{
Elementelem;
structLStack*next;
}*PLStack;
/*************棧函數****************/
intInitStack(PLStack
return1;
}
intStackEmpty(PLStackS)//判斷棧是否為空
{
if(S==NULL)
return1;
else
return0;
}
intPush(PLStack
p=(PLStack)malloc(sizeof(LStack));
p->elem=e;
p->next=S;
S=p;
return1;
}
intPop(PLStack
if(!StackEmpty(S))
{
e=S->elem;
p=S;
S=S->next;
free(p);
return1;
}
else
return0;
}
/***************求迷宮路徑函數***********************/
voidMazePath(structmarkstart,structmarkend,intmaze[M][N],intdiradd[4][2])
{
inti,j,d;inta,b;
Elementelem,e;
PLStackS1,S2;
InitStack(S1);
InitStack(S2);
maze[start.x][start.y]=2;//入口點作上標記
elem.x=start.x;
elem.y=start.y;
elem.d=-1;//開始為-1
Push(S1,elem);
while(!StackEmpty(S1))//棧不為空有路徑可走
{
Pop(S1,elem);
i=elem.x;
j=elem.y;
d=elem.d+1;//下壹個方向
while(d
{
a=i+diradd[d][0];
b=j+diradd[d][1];
if(a==end.x
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=886;//方向輸出為-1判斷是否到了出口
Push(S1,elem);
printf(\n0=東1=南2=西3=北886為則走出迷宮\n\n通路為:(行坐標,列坐標,方向)\n);
while(S1)//逆置序列並輸出迷宮路徑序列
{
Pop(S1,e);
Push(S2,e);
}
while(S2)
{
Pop(S2,e);
printf(-->(%d,%d,%d),e.x,e.y,e.d);
}
return;//跳出兩層循環,本來用break,但發現出錯,exit又會結束程序,選用return還是不錯滴
}
if(maze[a][b]==0)//找到可以前進的非出口的點
{
maze[a][b]=2;//標記走過此點
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);//當前位置入棧
i=a;//下壹點轉化為當前點
j=b;
d=-1;
}
d++;
}
}
printf(沒有找到可以走出此迷宮的路徑\n);
}
/*************建立迷宮*******************/
voidinitmaze(intmaze[M][N])
{
inti,j;
intm,n;//迷宮行,列[/M]
printf(請輸入迷宮的行數m=);
scanf(%d,
printf(請輸入迷宮的列數n=);
scanf(%d,
printf(\n請輸入迷宮的各行各列:\n用空格隔開,0代表路,1代表墻\n,m,n);
for(i=1;i
for(j=1;j
scanf(%d,
printf(妳建立的迷宮為(最外圈為墻)...\n);
for(i=0;i
{
maze[i][0]=1;
maze[i][n+1]=1;
}
for(j=0;j
{
maze[0][j]=1;
maze[m+1][j]=1;
}
for(i=0;i
{
for(j=0;j
printf(%d,maze[i][j]);
printf(\n);
}
}
voidmain()
{
intsto[M][N];
structmarkstart,end;//start,end入口和出口的坐標
intadd[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量方向依次為東西南北[/M]
initmaze(sto);//建立迷宮
printf(輸入入口的橫坐標,縱坐標[逗號隔開]\n);
scanf(%d,%d,
printf(輸入出口的橫坐標,縱坐標[逗號隔開]\n);
scanf(%d,%d,
MazePath(start,end,sto,add);//findpath
system(PAUSE);
}
測試數據,算法復雜度妳就自己來寫吧,如果妳連這都不自己做,那妳壹定是在應付作業。勸妳還是自己運行測試壹下吧,免得答辯時老師問妳,什麽都不知道,那妳就悲劇了。祝妳好運!!