定义一个二维数组： 

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 <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;
typedef pair<int, int> P;
const int N = 10;

int g[N][N];
int used[N][N];
P pre[N][N];    //记录前驱节点

int d[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};   // 四个方向

void bfs()
{
    queue<P> que;
    P p;
    p.first = p.second = 0;
    que.push(p);
    used[0][0] = 1;
    while(!que.empty())
    {
        p = que.front();    que.pop();
        // if(p.first == 4 && p.second == 4)
        //     return;
        for(int i=0; i<4; i++)
        {
            int dx = p.first + d[i][0];
            int dy = p.second + d[i][1];
            if(dx >= 0 && dx < 5 && dy >= 0 && dy < 5 && g[dx][dy] != 1 && used[dx][dy] != 1)
            {
                que.push(P(dx, dy));
                used[dx][dy] = 1;
                pre[dx][dy] = p;    // 记录当前节点的前驱节点
            }
        }
    }
}

vector<P> get_path(P p) // 获取路径
{
    vector<P> path;
    for( ; p.first != -1 && p.second != -1; p = pre[p.first][p.second])
        path.push_back(p);
    reverse(path.begin(), path.end());  // 得到的路径是逆序的，所以需要反转路径
    return path;
}

int main()
{
    for(int i=0; i<5; i++)
    {
        for(int j=0; j < 5; j++)
        {
            scanf("%d", &g[i][j]);
        }
    }
    memset(used, 0, sizeof(used));
    memset(pre, -1, sizeof(pre));    // 最好初始化为-1
    bfs();
    vector<P> path = get_path(P(4, 4));
    for(int i=0; i < path.size(); i++)
        printf("(%d, %d)\n", path[i].first,  path[i].second);
    

    return 0;
}