POJ 3984 迷宫问题（BFS）-白红宇

POJ 3984 迷宫问题（BFS）

阅读量：4316 次

发布时间：2019-06-06

本文共 2001 字，大约阅读时间需要 6 分钟。

迷宫问题

Description

定义一个二维数组：

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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

0 1 0 0 00 1 0 1 00 0 0 0 00 1 1 1 00 0 0 1 0

Sample Output

(0, 0)(1, 0)(2, 0)(2, 1)(2, 2)(2, 3)(2, 4)(3, 4)(4, 4)

题解：

本题首先想到BFS一遍，数组dis存最短路径（此方法来自《挑战程序设计竞赛(第2版)》-宽度优先搜索，迷宫最短路径-P34）。但没办法记录走过的路径，那该怎么办呢？

我想到的是开一个pair数组sha，记录此点的上一个点的x和y。之后开循环，根据本x，y继续找上个x，y。最后判断sha是否x==0，y==0，如果满足，那么就退出循环。

我把答案存在了sta栈里（其实也可以存在数组里，最后倒输出即可。但作为一个合格的IT男，能装逼则装逼，呵呵:-D）最后输出sta.top() 之后sta.pop() 最后答案即可求出。

AC代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 using namespace std;#define cle(a,b) memset(a,b,sizeof(a))#define rep(i,b) for(unsigned i=0;i<(b);i++)const int INF=9999;int a[5][5],dis[5][5],dx[]= {0,1,-1,0},dy[]= {1,0,0,-1};pair
                 
                   sha[5][5];struct node{ int x,y;};void bfs(){ queue
                  
                    que; node pre,next; pre.x=0; pre.y=0; dis[0][0]=0; que.push(pre); while(que.size()) { pre=que.front(); que.pop(); next=pre; for (int i=0; i<4; i++) { int nx=next.x+dx[i],ny=next.y+dy[i]; if (nx<5&&nx>=0&&ny<5&&ny>=0&&dis[nx][ny]==INF&&a[nx][ny]!=1) { dis[nx][ny]=dis[next.x][next.y]+1; node tem; tem.x=nx; tem.y=ny; sha[nx][ny].first=next.x; sha[nx][ny].second=next.y; que.push(tem); } } }}int main(){ rep(i,5) rep(j,5) { dis[i][j]=INF; sha[i][j].first=INF,sha[i][j].second=INF; scanf("%d",&a[i][j]); } bfs(); int xx=sha[4][4].first,yy=sha[4][4].second; stack< node > sta; while(xx!=0||yy!=0) { node te; te.x=xx; te.y=yy; sta.push(te); int nxx=xx,nyy=yy; xx=sha[nxx][nyy].first; yy=sha[nxx][nyy].second; } puts("(0, 0)"); while(sta.size()) { node pa; pa=sta.top(); printf("(%d, %d)\n",pa.x,pa.y); sta.pop(); } puts("(4, 4)"); return 0;}

转载于:https://www.cnblogs.com/s1124yy/p/5520995.html

你可能感兴趣的文章

php怎么设置文本区域,PHP txt下载不写文本区域内容