题解 | #迷宫问题#参考了别人的
迷宫问题
http://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc
广搜出路径，深搜出结果，深搜从终点开始递归找爹，起点就是递归终止条件
/*定义一个二维数组 N*M ，如 5 × 5 数组下所示：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，
只能横着走或竖着走，不能斜着走，要求编程序找出从左上
角到右下角的路线。入口点为[0,0],既第一格是可以走的路。
*/
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
typedef struct pos
{
int x;
int y;
}pos;
pos father[10][10];
void BFS(int a[][10],int n,int m,pos p)//二维数组做形参第二维或更高维的大小不可以省略
{
int visited[10][10]={0};
pos v;
pos W,A,S,D;
queue<pos>q;
q.push(p);
visited[p.x][p.y]=2;
while(!q.empty())
{
v=q.front();
W.x=v.x-1; W.y=v.y;//上
A.x=v.x; A.y=v.y-1;//左
S.x=v.x+1; S.y=v.y;//下
D.x=v.x; D.y=v.y+1;//右
q.pop();
if(W.x>=0&&W.x<n&&W.y>=0&&W.y<m&&a[W.x][W.y]==0&&visited[W.x][W.y]==0)
{
visited[W.x][W.y]=2;
q.push(W);
father[W.x][W.y]={v.x,v.y};
if(W.x==n-1&&W.y==m-1) break;
}
if(A.x>=0&&A.x<n&&A.y>=0&&A.y<m&&a[A.x][A.y]==0&&visited[A.x][A.y]==0)
{
visited[A.x][A.y]=2;
q.push(A);
father[A.x][A.y]={v.x,v.y};
if(A.x==n-1&&A.y==m-1) break;
}
if(S.x>=0&&S.x<n&&S.y>=0&&S.y<m&&a[S.x][S.y]==0&&visited[S.x][S.y]==0)
{
visited[S.x][S.y]=2;
q.push(S);
father[S.x][S.y]={v.x,v.y};
if(S.x==n-1&&S.y==m-1) break;
}
if(D.x>=0&&D.x<n&&D.y>=0&&D.y<m&&a[D.x][D.y]==0&&visited[D.x][D.y]==0)
{
visited[D.x][D.y]=2;
q.push(D);
father[D.x][D.y]={v.x,v.y};
if(D.x==n-1&&D.y==m-1) break;
}
}
// for(int i=0;i<n;i++)
// {
// for(int j=0;j<m;j++)
// {
// cout<<"f:"<<father[i][j].x<<","<<father[i][j].y<<" ";
// }
// cout<<endl;
// }
}
void dfs(pos p)
{
pos q;
if(p.x==0&&p.y==0) return;
q=father[p.x][p.y];
dfs(q);
cout<<"("<<p.x<<","<<p.y<<")"<<endl;
}
int main()
{
int a[10][10];
int n,m;
cin>>n>>m;
pos p={0,0};
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
}
}
// cout<<"bfs:"<<endl;
BFS(a,n,m,p);
pos t={n-1,m-1};
cout<<"(0,0)"<<endl;
dfs(t);
}
