Problem Descrption

Promble 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

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

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

問題鏈接：http://poj.org/problem?id=3984
問題分析：之前利用DFS的模板坐過一次，最近試著用BFS的算法做了一次，BFS效率較高，用到隊列queue

AC代碼：

#include<iostream> #include<stdio.h> #include<cstring> #include<queue> using namespace std; int n[4][2] = { 1,0,0,1,-1,0,0,-1 }; int vis[5][5]; int map[5][5]; struct id {int x, y; }; struct id ed[5][5]; void BFS() {struct id t;queue<id>q;t.x = 0, t.y = 0;q.push(t);vis[0][0] = 1;ed[0][0].x = 0;ed[0][0].y = 0;while (!q.empty()){struct id a = q.front();if (a.x == 4 && a.y == 4)return;q.pop();for (int i = 0; i < 4; i++){int tx = a.x + n[i][0], ty = a.y + n[i][1];if (tx < 0 || ty < 0 || tx>4 || ty>4 || vis[tx][ty]||map[tx][ty])continue;struct id b;b.x = tx, b.y = ty;q.push(b);vis[tx][ty] = 1;ed[tx][ty].x = a.x;ed[tx][ty].y = a.y;}}} int main() {for (int i = 0; i < 5; i++)for (int j = 0; j < 5; j++)scanf("%d", &map[i][j]);BFS();int m[30][2], t = 0,x=4,y=4,p;while (1){m[t][0] = x, m[t][1] = y;t++;if(x == 0 && y == 0)break;p = x;x = ed[x][y].x, y = ed[p][y].y;}for (int i = t-1; i >= 0; i--){printf("(%d, %d)\n", m[i][0], m[i][1]);} }

附上詳細注釋的他人的代碼：

本篇先以一道題的題解來說明問題模板可以大體分成6部分 1.頭文件段 2.坐標結構體段 3.障礙物預設段 4.已訪問結點和移動坐標段 5.BFS算法函數段 6.主函數段定義一個二維數組： 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 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 Sample Output (0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)1.頭文件段 //這里使用c++的<queue>函數，這樣可以快速進行隊列的操作，沒啥好解釋的，背下 #include<iostream> using namespace std; #include<stdio.h> #include<string.h> #include<queue>2.坐標結構體段 //記錄結點坐標，特別注意，這里的坐標也可能是一維的，不要死板，具體情況具體分析。 struct mi{int x;int y; }ca;3.障礙物預設段（有可能沒有，是無障礙題目） //這里往往是初始化好的迷宮地圖，或是什么其他條件的障礙物,在這里1就是障礙物, 這個地圖要么是自己輸入，要么是題目已知條件 int map[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},} struct mi zhen[5][5]; //這里記錄著路徑子節點與父節點的對應關系在5中詳解4.已訪問結點和移動坐標段 //注意移動坐標要一一對應，可以使用二維數組，代表著在迷宮中怎樣移動 int visited[5][5]; //用來記錄已訪問節點，但是也可以不要這個數組，每次走到后直接改變圖， 把此節點的內容直接變成障礙物即可 int xx[4]={1,-1,0,0}; int yy[4]={0,0,-1,1};5.BFS算法函數段 //這里主要是對BFS算法的套用,具體可以看下列詳細注釋 注意：凡是寫到背下的，說明其基本可以完全復用，而且處于此模板的核心部分void BFS() {memset(visited,0,sizeof(visited)); //背下，初始化已訪問數組queue<mi>q; //背下,初始化隊列struct mi A; //背下，把第一個結點壓入隊列里A.x=0; //初始化第一個節點坐標 沒啥好說的A.y=0; visited[0][0]=1; //初始化首已訪問節點，說明自己已被訪問zhen[0][0].x=0; //初始化對應關系底層結點 下面將詳細解釋zhen[0][0].y=0;//特別注意:千萬不要死板，此題是走迷宮，所以首節點是左上角，其他題可不一定，千萬不要一堆0就上去了q.push(A); //將首節點壓入隊列 while(!q.empty()) //背下，只要隊列里還有東西就繼續{struct mi te=q.front(); //這兩句背下q.pop();if(te.x==4&&te.y==4) //找到答案后退出 return;//特別注意:不一定都需要退出條件，如果題目要求我們對單節點進行移動（后面會提到）for(int i=0;i<4;i++) //背下，把各個方向都試著走一遍{int zx=te.x+xx[i]; //zx,zy為移動后節點坐標int zy=te.y+yy[i];if(zx<0||zx>4||zy<0||zy>4||map[zx][zy]||visited[zx][zy]) //背下，判斷是否為合法路徑，比如墻和已走過節點都為非法路徑，但讓我前面提到過，可以把已走過節點直接在地圖上變成墻也行，這樣就不需要visited數組continue;visited[zx][zy]=1; //將已訪問節點標志為1 下標對應當前節點struct mi kao; //背下，將合法子節點壓入隊列kao.x=zx;kao.y=zy;q.push(kao);//記錄著誰走到了它zhen[zx][zy].x=te.x; //現在來說明這個二維數組怎樣記錄最短路徑，首先這個數組里存的是坐標結構體，數組下標代表著子節點坐標，而數組內容存著父節點坐標，這樣皆可以通過循環，一級一級找上去，既可以知道最短路徑長度，也可以打印所有經過的節點坐標zhen[zx][zy].y=te.y;}} }6.主函數部分 //略寫 這沒什么好說的 根據題目要求不同這個地方的靈活性也最大 int main(void) {for(int m=0;m<5;m++) //初始化迷宮地圖{for(int n=0;n<5;n++){scanf("%d",&map[m][n]);}}BFS(); int num[30][2];int x=4,y=4;int i=0;while(1){ //把父子節點關系倒著取出放入數組中以便打印int k;k=x;x=zhen[x][y].x;y=zhen[k][y].y;num[i][0]=x;num[i][1]=y; i++;if(x==0&&y==0)break;}for(int j=i-1;j>=0;j--){printf("(%d, %d)\n",num[j][0],num[j][1]); //打印路徑節點部分}printf("(4, 4)"); return 0; } --------------------- 作者：jiange702 來源：CSDN 原文：https://blog.csdn.net/jiange702/article/details/81365005 版權聲明：本文為博主原創文章，轉載請附上博文鏈接！

?

總結

以上是生活随笔為你收集整理的POJ3904（BFS算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。