/*
题目：
求最少时间从(0,0)走到(4,4)的路径
分析：
纯粹BFS题目，不过需要打印路径，可以用数组记录当前的坐标的上一个坐标，
因为BFS构造出一棵BFS最优生成树，每一个节点的父母节点都是唯一的，具体
参考算法导论。。。
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
#define X 6
int map[X][X],pre[X][X];
bool visit[X][X];
struct node
{
int x,y;
};
void print(int x,int y) //打印路径
{
if(x||y) //一直递归到起始的(0,0)为止，然后不停输出到(4,4)走过的路
print(pre[x][y]/10,pre[x][y]%10);
if(pre[x][y]!=-1&&pre[x][y]!=-1) //不输出(0,0)以前的坐标。。。
printf("(%d, %d)\n",pre[x][y]/10,pre[x][y]%10);
}
void bfs()
{
queue<node> q;
node temp,cur;
temp.x = 0;
temp.y = 0;
q.push(temp);
int x,y;
visit[0][0] = true;
while(!q.empty()) //BFS核心
{
cur = q.front();
q.pop();
x = cur.x;
y = cur.y;
if(x==4&&y==4)
print(4,4);
if(x&&!visit[x-1][y]&&!map[x-1][y])//往上走
{
visit[x-1][y] = true;
temp.x = x-1;
temp.y = y;
pre[x-1][y] = x*10+y;
q.push(temp);
}
if(y&&!map[x][y-1]&&!visit[x][y-1]) //往左走
{
visit[x][y-1] = true;
temp.x = x;
temp.y = y-1;
pre[x][y-1] = x*10+y;
q.push(temp);
}
if(y<4&&!map[x][y+1]&&!visit[x][y+1])//往右走
{
visit[x][y+1] = true;
temp.x = x;
temp.y = y+1;
pre[x][y+1] = x*10+y;
q.push(temp);
}
if(x<4&&!map[x+1][y]&&!visit[x+1][y])//往下走
{
visit[x+1][y] = true;
temp.x = x+1;
temp.y = y;
pre[x+1][y] = x*10+y;
q.push(temp);
}
}
}
int main()
{
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
while(cin>>map[0][0])
{
memset(pre,-1,sizeof(pre));
memset(visit,false,sizeof(visit));
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
if(i||j)
scanf("%d",&map[i][j]);
bfs();
printf("(%d, %d)\n",4,4);//最后打印最后的坐标
}
return 0;
}