//應(yīng)用棧來(lái)走迷宮
#include<stdio.h>
#include<stdlib.h>
struct stack_node
{
int x;//路徑坐標(biāo)x
int y;//路徑坐標(biāo)y
struct stack_node *next;//指向下一結(jié)點(diǎn)
};
typedef struct stack_node stack_list;
typedef stack_list *link;
link path=NULL;//路徑棧指針
//棧數(shù)據(jù)的存入
link push(link stack,int x,int y)
{
link new_node;//新結(jié)點(diǎn)指針
//分配結(jié)點(diǎn)內(nèi)存
new_node=(link)malloc(sizeof(stack_list));
if(!new_node)
{
printf("內(nèi)存分配失敗!\n");
return NULL;
}
new_node->x=x; //存入路徑坐標(biāo)x
new_node->y=y; //存入路徑坐標(biāo)y
new_node->next=stack;//新結(jié)點(diǎn)指向原開(kāi)始
stack=new_node; //新結(jié)點(diǎn)成為棧開(kāi)始
return stack;
}
//棧數(shù)據(jù)的取出
link pop(link stack,int *x,int *y)
{
link top;//指向棧頂端
if(stack!=NULL)
{
top=stack;
stack=stack->next;//棧指針指向下結(jié)點(diǎn)
*x=stack->x;//取出路徑坐標(biāo)x
*y=stack->y;//取出路徑坐標(biāo)y
free(top);
return stack;
}
else
*x=-1;
}
//主程序：用回溯的方法在數(shù)組迷宮找出口
//數(shù)字0:表示是可以走的路
//數(shù)字1:表示是墻壁，不可走的路
//數(shù)字2:表示是走過(guò)的路
//數(shù)字3:表示是回溯的路
void main()
{
int maze[7][10]={
1,1,1,1,1,1,1,1,1,1,
1,0,1,0,1,0,0,0,0,1,
1,0,1,0,1,0,1,1,0,1,
1,0,1,0,1,1,1,0,0,1,
1,0,1,0,0,0,0,0,1,1,
1,0,0,0,1,1,1,0,0,1,
1,1,1,1,1,1,1,1,1,1,};
int i,j;
int x=5;//迷宮入口坐標(biāo)
int y=8;
while(x!=1||y!=1)//是否是迷宮出口
{
maze[x][y]=2;//標(biāo)示走過(guò)的路
if(maze[x-1][y]<=0) //往上方走
{
x=x-1;
path=push(path,x,y);//存入路徑
}
else if(maze[x+1][y]<=0)//往下方走
{
x=x+1;
path=push(path,x,y);
}
else if(maze[x][y-1]<=0)//往左方走
{
y=y-1;
path=push(path,x,y);
}
else if(maze[x][y+1]<=0)//往右方走
{
y=y+1;
path=push(path,x,y);
}
else
{
maze[x][y]=3;
path=pop(path,&x,&y);//退回一步
}
}
maze[x][y]=2;
printf("迷宮的路徑如下圖所示:\n");
for(i=1;i<6;i++)//輸出迷宮圖形
{
for(j=1;j<9;j++)
printf("%d",maze[i][j]);//輸出各坐標(biāo)
printf("\n");
}
}