迷宫问题：BFS

原文地址：http://blog.csdn.net/u013480600/article/details/25486071

POJ 3984 迷宫问题(BFS:迷宫最短路径且输出路径)

http://poj.org/problem?id=3984

题意：

定义一个二维数组： 

int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

分析:

        典型的BFS应用,要你求从左上角到右下角的最短路径,且保证有唯一解,且要输出路径.

        直接BFS求解即可,需要用到vis数组和dist数组,用pre数组来保存当前节点的最短路径上的前一个点(或方向也行).

        其实也可以不用pre数组的,可以直接倒推出最短路径.

AC代码:

[cpp]  view plain  copy #include<cstdio>   #include<cstring>   #include<algorithm>   #include<queue>   #include<stack>   using namespace std;   int maze[10][10];   int vis[10][10],dist[10][10];   int dr[]={-1,1,0,0};//上,下,左,右   int dc[]={0,0,-1,1};   struct Node   {       int r,c;//也可以在Node中加一个int pre属性,然后做一个全局的nodes,就不用pre[][]数组了.       Node(int r,int c):r(r),c(c){}       Node(){}   }pre[10][10];   queue<Node> Q;   void BFS()   {       while(!Q.empty()) Q.pop();       memset(vis,0,sizeof(vis));       dist[0][0]=0;       vis[0][0]=1;       Q.push(Node(0,0));       while(!Q.empty())       {           Node node=Q.front();Q.pop();           int r=node.r,c=node.c;           for(int d=0;d<4;d++)           {               int nr=r+dr[d];               int nc=c+dc[d];               if(nr>=0&&nr<5&&nc>=0&&nc<5&&vis[nr][nc]==0&&maze[nr][nc]==0)               {                   vis[nr][nc]=1;                   Q.push(Node(nr,nc));                   dist[nr][nc]=1+dist[r][c];                   pre[nr][nc]=Node(r,c);                   if(nr==4&&nc==4) return ;               }           }       }   }   int main()   {       for(int i=0;i<5;i++)           for(int j=0;j<5;j++)               scanf("%d",&maze[i][j]);       BFS();       stack<Node> S;       int cur_r=4,cur_c=4;       while(true)       {           S.push(Node(cur_r,cur_c));           if(cur_r==0&&cur_c==0) break;           int r=cur_r,c=cur_c;           cur_r=pre[r][c].r;           cur_c=pre[r][c].c;       }       while(!S.empty())       {           Node node=S.top(); S.pop();           printf("(%d, %d)\n",node.r,node.c);       }       return 0;   }