Question

深度优先搜索迷宫问题求解

#include <stdio.h>
int n,mg[13][13],sf=0;
int dx[]={-1,0,1,0};int dy[]={0,1,0,-1};
void DFS(int x1,int x2)
{
int i,r,c;
if(x1==n-1&&x2==n-1){sf=1;}
else
{
mg[x1][x2]=1;
for(i=0;i<4;i++)
{
r=x1+dx[i];c=x2+dy[i];
if(r>0&&r<n-1&&c>0&&c<n-1&&mg[r][c]==0)
{
mg[r][c]=1;
DFS(r,c);
mg[r][c]=0;
}
mg[x1][x2]=0;
}
}
}
void main()
{
int i,j;
scanf("%d",&n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
scanf("%d",&mg[i][j]);
}
DFS(0,0);
if(sf=1){printf("YES");}
else{printf("NO");}
}

1是障碍，0是通路，如果有路输出YES，否则NO。
但是不管怎么输都是YES，为什么

Answer 1

要用深度优先和广度优先两种方法实现。找到的那条路径一定是最短的。问题补充很久以前做的，现在都忘记了。你看一下吧。我的报告，也可以发给你，不过

Answer 2

- -

追问

??