原题：http://bailian.openjudge.cn/practice/4127/
描述
定义一个二维数组：
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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
输入
一个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
样例输出
(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)
解放
思路：广搜，用队列，由于需要输出路径，所以用class来记录父节点。
#include <iostream> #include <queue> using namespace std; class path { public: int x; int y; path* parent; path() { x = 0; y = 0; parent = NULL; } }; int maze[5][5]; int dx[4] = { 1,-1,0,0 }; int dy[4] = { 0,0,1,-1 }; void output(path* p) { if (p->x == 0 && p->y == 0) cout << "(0, 0)" << endl; else { output(p->parent); cout << "(" << p->x << ", " << p->y << ")" << endl; } } int main() { for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) cin >> maze[i][j]; path* begin = new path;; queue<path*>ds; ds.push(begin); while (!ds.empty()) { path* top = ds.front(); if (top->x == 4 && top->y == 4) break; maze[top->x][top->y] = 1; ds.pop(); for (int i = 0; i < 4; i++){ int tempx = top->x + dx[i]; int tempy = top->y + dy[i]; if (tempx < 0 || tempx >= 5 || tempy < 0 || tempy >= 5) continue; if (maze[tempx][tempy] == 1) continue; path* temp = new path; temp->x = tempx; temp->y = tempy; temp->parent = top; ds.push(temp); } } path* top = ds.front(); output(top); return 0; }
按照进度，本来还没到广搜，但是一顺手就把这个题给做了，等到复习完广搜应该有更简洁的代码实现。