/*
定义一个二维数组： 

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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
这里最短路径好求,BFS即可，但是如何保存路径是个问题，在这里我采用了一次BFS，即从终点向起点搜索同时用stack保存路径上的点。
*/
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
struct node
{
    int x;
    int y;
    int step;
};
int g[5][5];
int been[5][5];
int dis[5][5];
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
stack<node> S;
bool judge(int x,int y)
{
    if(!g[x][y]&&!been[x][y]&&x>=0&&y>=0&&x<5&&y<5)
        return true;
    return false;
}
void Read()
{
    int i,j;
    for(i=0;i<5;i++)
        for(j=0;j<5;j++)
            cin>>g[i][j];
}
int bfs(int i,int j)
{
    node a;
    a.x = i;
    a.y = j;
    a.step = 0;
    been[i][j] = 1;
    dis[i][j] = 0;
    queue<node> Q;
    Q.push(a);
    while(!Q.empty())
    {
        node temp = Q.front();
        Q.pop();
        if(temp.x==4&&temp.y==4)
            return temp.step;
        for(int i =0;i<4;i++)
        {
            if(judge(temp.x+dir[i][0],temp.y+dir[i][1]))
            {
                node new_node;
                new_node.x = temp.x+dir[i][0];
                new_node.y = temp.y+dir[i][1];
                new_node.step = temp.step + 1;
                been[new_node.x][new_node.y] = 1;
                Q.push(new_node);
                if(dis[new_node.x][new_node.y] > temp.step + 1)
                    dis[new_node.x][new_node.y]=temp.step + 1;
            }
        }
    }
    return -1;
}
void route(int i,int j,int d);
int main()
{
    int i,j,ans;
    for(i = 0;i<5;i++)
        for(j=0;j<5;j++)
            dis[i][j] = 1000;
    Read();
    ans = bfs(0,0);
    route(4,4,ans);
    while(!S.empty())
    {
        node p = S.top();
        S.pop();
        cout<<‘(‘<<p.x<<‘,‘<<‘ ‘<<p.y<<‘)‘<<endl;
    }
    cout<<‘(‘<<4<<‘,‘<<‘ ‘<<4<<‘)‘<<endl;
    return 0;
}
void route(int i,int j,int d)
{
    if(i==0&&j==0)
    {
        return ;
    }
    else
    {
        for(int k =0;k<4;k++)
        {
            int r = i+dir[k][0],c = j+dir[k][1];
            if(r>=0&&c>=0&&r<5&&c<5&&(dis[r][c]==d-1)&&(been[r][c]))
            {
                node ct;
                ct.x = r;
                ct.y = c;
                S.push(ct);
                route(r,c,d-1);
            }
        }
    }
    return ;
}