走出迷宫

　　在很久很久以前，有一位大师级程序员，实力高强，深不可测，代码能力无人能及。从来没有人听说过他的真名，只知道他在完成一段代码后，总会跟上一行注释“十四出品，必属精品”，于是他在编程江湖上便有了绰号“十四”。

　　随着十四大师声名远播，意图登门拜访，寻求编程秘法的人也渐渐多了起来。然而，正如他无人知晓的真名一般，十四大师的真面目也少有人得见。这并不是因为大师住处隐秘，而是因为大师居所前有着他亲自布下的阵法，它困住了无数虔诚的求知者。

　　作为十四大师崇拜者的小胖经过苦心探寻，终于有一天得到了法阵的地图。

　　地图显示，法阵是方形的，纵横皆为五里，在地图上简示为5*5的矩阵，且只由0或1组成。其中，0表示可以走的路，1表示阻止通行的屏障。左上角和右下角分别是阵的入口和出口，这两个位置的数字保证为0。

　　既然得到了地图，破解法阵自然不再是难事。现在，小胖不仅想要走出法阵，还想知道怎样才能用最短的路线走出法阵。

Input
　　输入是一个5 × 5的二维数组，仅由0、1两数字组成，表示法阵地图。

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)

Hint
　　坐标(x, y)表示第x行第y列，行、列的编号从0开始，且以左上角为原点。

　　另外注意，输出中分隔坐标的逗号后面应当有一个空格。

bfs求最短路径，加上一个路径记录。CLion有毒，编译错误了好几次，就是练的少，还懒，生气，醒来就12点了，这要少了多少时间，生气。

//
// Created by sequin on 2/16/17.
//
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int mv[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
int grp[5][5];
bool vis[5][5];
queue <pair<int, int> > q;
pair <int , int> now;
pair<int, int> path[5][5];

void bfs(){
    memset(vis, false, sizeof(vis));
    while(!q.empty())
        q.pop();

    vis[0][0] = true;
    q.push(make_pair(0, 0));

    while(!q.empty()){
        pair <int, int> tmp = (pair<int, int> &&) q.front();
        q.pop();
        int x = tmp.first;
        int y = tmp.second;

        for (int i = 0; i < 4; ++i) {
            int xx = x + mv[i][0];
            int yy = y + mv[i][1];
            if(xx < 0 || yy < 0 || xx >= 5 || yy >= 5){
                continue;
            }
            if(grp[xx][yy] == 1){
                continue;
            }
            if(vis[xx][yy]){
                continue;
            }
            vis[xx][yy] = true;
            now.first = xx;
            now.second = yy;
            q.push(make_pair(xx, yy));
            path[x][y] = now;
        }
    }

    now.first = now.second = 0;
    while(now.first != 4 || now.second != 4){
        printf("(%d, %d)\n", now.first, now.second);
        now = path[now.first][now.second];
    }
    printf("(4, 4)\n");
}

int main(){
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; ++j) {
            cin >> grp[i][j];
        }
    }
    bfs();
}