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 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)

求最短路徑既是廣搜思想，可用數組模擬隊列，直到隊列為空或者找到目標節點即結束，代碼如下：

#include<iostream> #include<stdio.h>using namespace std;struct node{int x;int y;int pre; }path[100];int dirx[4]={0,0,1,-1}; int diry[4]={1,-1,0,0};int map[5][5]; int front=0,rear=1;void print(int i){if(path[i].pre!=-1){ //找到始點后再開始輸出節點 print(path[i].pre);printf("(%d, %d)\n",path[i].x,path[i].y); }elseprintf("(%d, %d)\n",path[i].x,path[i].y); } void WFS(int x, int y){path[front].x=x;path[front].y=y;path[front].pre=-1;map[x][y]=1;bool flag=false;while(front<rear){for(int i=0; i<4; ++i){int px=path[front].x+dirx[i];int py=path[front].y+diry[i];if(px<0||py<0||px>4||py>4||map[px][py])continue;else{map[px][py]=1;path[rear].x=px; //入隊 path[rear].y=py;path[rear].pre=front;rear++;}if(px==4 && py==4){print(rear-1);flag=true;break;}}front++;if(flag)break;} }int main(){for(int i=0;i<5;++i)for(int j=0; j<5; ++j)scanf("%d",&map[i][j]);WFS(0,0); return 0; }

總結

以上是生活随笔為你收集整理的Poj_3984走迷宫(广搜)的全部內容，希望文章能夠幫你解決所遇到的問題。

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