#include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; struct Node{ int x,y; Node(){ x = 0; y = 0; } Node(int a,int b){ x = a; y = b; } }; int data[5][5]; Node pre[5][5]; void print(){ Node u(4,4); vector<Node>nodes; for(;;){ nodes.push_back(u); if(u.x==0&&u.y==0)break; u = pre[u.x][u.y]; } for(int i=nodes.size()-1;i>=0;i--){ printf("(%d, %d)\n",nodes[i].x,nodes[i].y); } } void bfs(){ int i; queue<Node>q; int d[5][5]; memset(d,-1,sizeof d); Node u(0,0); d[0][0] = 0; q.push(u); while(!q.empty()){ Node u = q.front();q.pop(); if(u.x==4&&u.y==4){ print(); return; } if(u.x+1<5&&data[u.x+1][u.y]==0&&d[u.x+1][u.y]==-1){ d[u.x+1][u.y] = d[u.x][u.y] + 1; pre[u.x+1][u.y] = u; q.push(Node(u.x+1,u.y)); } if(u.x-1>=0&&data[u.x-1][u.y]==0&&d[u.x-1][u.y]==-1){ d[u.x-1][u.y] = d[u.x][u.y] + 1; pre[u.x-1][u.y] = u; q.push(Node(u.x-1,u.y)); } if(u.y+1<5&&data[u.x][u.y+1]==0&&d[u.x][u.y+1]==-1){ d[u.x][u.y+1] = d[u.x][u.y] + 1; pre[u.x][u.y+1] = u; q.push(Node(u.x,u.y+1)); } if(u.y-1>=0&&data[u.x][u.y-1]==0&&d[u.x][u.y-1]==-1){ d[u.x][u.y-1] = d[u.x][u.y] + 1; pre[u.x][u.y-1] = u; q.push(Node(u.x,u.y-1)); } } } int main(){ int i,j; for(i=0;i<5;i++){ for(j=0;j<5;j++){ scanf("%d",&data[i][j]); } } bfs(); return 0; }