Description
定义一个二维数组:
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
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)
问题分析:依然是本应该用dfs的问题但我用的是bfs。。。通过在地图上记录上一个节点并从终点开始走,可以得到路径。
#include "cstdio" #include "iostream" #include "queue" using namespace std; int a[5][5]; struct person { int i; int j; }; void abegin() { for (int i=0;i<5;i++) for (int j=0;j<5;j++) cin>>a[i][j]; } void print() { int i=0,j=0; printf ("(%d, %d) ",i,j); while (i != 4 || j != 4) { switch(a[i][j]) { case 3: i--; break; case 4: i++; break; case 5: j--; break; case 6: j++; break; default: continue; } printf ("(%d, %d) ",i,j); } } void bfs () { queue<person> p; person fir,sec; fir.i = 4; fir.j = 4; a[fir.i][fir.j] = 2; p.push(fir); while (!p.empty()) { sec = p.front(); p.pop(); if (sec.i>0 && a[sec.i-1][sec.j] < 1) { fir.i=sec.i-1; fir.j=sec.j; a[fir.i][fir.j] = 4; p.push(fir); } if (sec.i<4 && a[sec.i+1][sec.j] < 1) { fir.i=sec.i+1; fir.j=sec.j; a[fir.i][fir.j] = 3; p.push(fir); } if (sec.j>0 && a[sec.i][sec.j-1] < 1) { fir.i=sec.i; fir.j=sec.j-1; a[fir.i][fir.j] = 6; p.push(fir); } if (sec.j<4 && a[sec.i][sec.j+1] < 1) { fir.i=sec.i; fir.j=sec.j+1; a[fir.i][fir.j] = 5; p.push(fir); } if (a[0][0] != 0) { print (); return; } } } int main() { abegin(); bfs(); return 0; }