题目

定义一个二维数组：

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<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX = 10;
int a[MAX][MAX];
bool book[MAX][MAX];
const int dr[] = { 0,0,1,-1 };
const int dc[] = { 1,-1,0,0 };
struct node { int x, y; node(int x, int y) :x(x), y(y) {} node() :x(0), y(0) {} };
node parent[MAX][MAX];

bool operator !=(const node &a, const node &b)
{
    return a.x != b.x || a.y != b.y;
}

void BFS(node n)
{
    fill(book[0], book[0] + MAX * MAX, false);
    queue<node> q;
    q.push(n);
    book[n.x][n.y] = true;
    while (!q.empty()) {
        node cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int r = cur.x + dr[i];
            int c = cur.y + dc[i];
            if (r < 0 || r >= 5 || c < 0 || c >= 5 || a[r][c] == 1) continue;
            if (!book[r][c]) {
                book[r][c] = true;
                node t = node(r, c);
                parent[r][c] = cur;//记录父节点
                q.push(t);
            }
        }
    }
}

void serchPath(node t, vector<node> &paths)//搜寻路径，（其实就是从尾节点原路返回到根节点）
{
    paths.push_back(t);
    node s = t;
    while (parent[s.x][s.y] != s) {
        s = parent[s.x][s.y];
        paths.push_back(s);
    }
    reverse(paths.begin(), paths.end());//因为是逆序，所以再倒过来就是正序了
}

int main()
{
    int u = 0;
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            cin >> a[i][j];
        }
    }
    vector<node> path;
    BFS(node(0, 0));
    serchPath(node(4, 4), path);
    for (int i = 0; i < path.size(); i++)
        cout << "(" << path[i].x << ", " << path[i].y << ")\n";
    return 0;
}