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来解决，这里需要注意的是结构体里要定义一个字符串变量用来保存走过的路。
#include#include #include using namespace std;#define MAXN 10//定义方向，顶部开始，顺时针int dir[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}};int a[MAXN][MAXN];//作用:标记,走过的结点标记为1int vis[MAXN][MAXN];struct Node{ int x; int y; string s; //字符串s保存走过的结点}now, nextStep;//判断结点能否通过bool isPracticable(Node node){ //当超出边界，或者已经被标记访问过，或者遇到障碍物都不能再通过 if (node.x < 0 || node.x > 5 || node.y < 0 || node.y > 5 || vis[node.x][node.y] || a[node.x][node.y]) { return 0; } return 1;}void BFS(){ queue Q; now.x = 0; now.y = 0; now.s = "00"; Q.push(now); vis[now.x][now.y] = 1; while (!Q.empty()) { //获取队列首部元素 now = Q.front(); if (now.x == 4 && now.y == 4) { //走到右下角，输出结果 for (int i = 0; i < now.s.length(); i = i + 2) { cout << "(" << now.s[i] << ", " << now.s[i+1] << ")" << endl; } return; } for (int i = 0; i < 4; i++) { //按照上、右、下、左的方向搜索，搜索方向可随意，但是要保证四个方向都被搜索一遍 nextStep.x = now.x + dir[i][0]; nextStep.y = now.y + dir[i][1]; nextStep.s = now.s; if (isPracticable(nextStep)) { char x = nextStep.x + 48; char y = nextStep.y + 48; nextStep.s += x; nextStep.s += y; Q.push(nextStep); vis[nextStep.x][nextStep.y] = 1; } } //把对首元素排出队列 Q.pop(); }}int main(int argc, const char * argv[]) { for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { cin >> a[i][j]; } } BFS(); return 0;}