POJ 3984 迷宮問題
迷宮問題
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 8089
Accepted: 4765
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)
本題關鍵在於輸出路徑，，方法是利用一個father數組記錄父節點，再逆向存入新的數組，正向輸出。
father[nx*5+ny]=p.first*5+p.second;
a[j++]=father[k];
k=father[k];
這裡形成一中環環相扣，最後一個數組是father[24]{4,4}它存儲著上一個位置的值x*5+y，而這一個又存儲著它的上一個。。。直到k=0{0,0}。
#include
#include
using namespace std;
int maze[5][5];
int d[5][5];
const int INF=1000;
int father[30];
typedef pair P;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
void print()
{
int a[30];
int j=0,k=24;
while(k!=0)
{
a[j++]=father[k];
k=father[k];
}
for(int i=j-1;i>=0;i--)
cout<<"(">maze[i][j];
bfs(0,0);
return 0;
}
這裡通過一個二維數組記錄（d[nx][ny]=d[p.first][p.second]+1;）到達每個位置所需行走的最短長度，，可以返回最短路徑值，但本題不作要求。
