#include<stdio.h>
#include<stdlib.h>
#define N 50
int **maze;
int row;
int col;
int stack[50];//存放路徑的棧
void CreateMaze()//用於動態創建迷宮
{
int i,j;
printf("請輸入迷宮的行數：");
scanf("%d",&row);
printf("請輸入迷宮的列數：");
scanf("%d",&col);
if(row<=0||col<=0)
{
printf("輸入的行數或列數不符合規則！\n");
exit(1);
}
//利用指針的指針動態創建二維數組
maze=(int **)malloc((row+2)*sizeof(int *));
for(i=0;i<row+2;i++)
{
maze[i]=(int *)malloc((col+2)*sizeof(int));
}
//加邊墻
for(i=0;i<row+2;i++)
{
maze[i][0]=1;
maze[i][col+1]=1;
}
for(i=0;i<col+2;i++)
{
if(i==1)
{
maze[0][i]=0;
}
else maze[0][i]=1;
if(i==col)
{
maze[row+1][col]=0;
}
else maze[row+1][i]=1;
}
for(i=1;i<=row;i++)
{
for(j=1;j<=col;j++)
{
printf("請輸入第%d行的第%d個數:\n",i,j);
scanf("%d",&maze[i][j]);
}
}
//輸入下壹個當前加邊墻的迷宮，以驗證輸入是否正確
printf("輸入完畢！當前加邊墻的迷宮為：\n");
for(i=0;i<row+2;i++)
{
for(j=0;j<col+2;j++)
{
printf("%d",maze[i][j]);
}
printf("\n");
}
}
void ShowMaze()//輸出迷宮
{
int i,j;
for(i=1;i<=row;i++)
{
for(j=1;j<=col;j++)
{
printf("%d",maze[i][j]);
}
printf("\n");
}
}
//釋放迷宮數組
void DestroyMaze()
{
int i;
for(i=0;i<row+2;i++)
free(maze[i]);
free(maze);
}
//用DFS方法來實現回溯，找到迷宮的壹條解路徑
int FindPath()
{
int i,j,k,count,x,y,direction;
count=0;
x=1,y=1;
direction=0;
j=0,k=0;
for(i=0;i<N;i++)
{
stack[i]=0;
}
i=0;
while(1)
{
count=0;//用count判斷是否有路可走
{
if(x==1&&y==1)
maze[x][y]=2;
if(maze[x][y+1]==0)//東
{
count++;
maze[x][y+1]=2;
y=y+1;
stack[i]=-1;
i++;
if(x==row&&y==col)
return 1;
}
else if(maze[x+1][y]==0)//南
{
if(maze[x+1][y]==0)
count++;
{
maze[x+1][y]=2;
x=x+1;
stack[i]=-2;
i++;
if(x==row&&y==col)
return 1;
}
}
else if(maze[x][y-1]==0)//西
{
count++;
if(maze[x][y-1]==0)
{
maze[x][y-1]=2;
y=y-1;
stack[i]=-3;
i++;
if(x==row&&y==col)
return 1;
}
}
else if(maze[x-1][y]==0)//北
{
count++;
if(maze[x-1][y]==0)
{
maze[x-1][y]=2;
x=x-1;
stack[i]=-4;
i++;
if(x==row&&y==col)
return 1;
}
}
}
if(count==0)
{
if(i<0)
return 0;
direction=stack[i--];
switch(direction)
{
case -1:y=y-1;break;
case -2:x=x-1;break;
case -3:y=y+1;break;
case -4:x=x+1;break;
default:break;
}
}
}
}
int main()
{
CreateMaze();
if(FindPath())
{
printf("已經找到了壹條路徑，如下:\n");
ShowMaze();
}
else
{
printf("沒有合適的路徑走出當前迷宮！\n");
}
DestroyMaze();
}