1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 struct node 8 { 9     int x;10     int y;11     int s;12 };13 int g[10][10];14 int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};15 int main()16 {17 //    freopen("in.in","r",stdin);18     node s, t;19     string l;20     queue<node>q;21     vector<node>v;22     23     for(int i = 0; i <= 6; i++)24         for(int j = 0; j <= 6; j++)25             g[i][j] = 1;    26             27     for(int i = 1; i <= 5; i++)28         for(int j = 1; j <= 5; j++)29             scanf("%d",&g[i][j]);        30 31     s.x = 1;32     s.y = 1;33     s.s = -1;34     q.push(s);35     while(q.size())36     {37         s = q.front();38         q.pop();39         g[s.x][s.y] = s.s;40         if(s.x == 5 && s.y == 5)    break;41         42         for(int i = 0; i < 4; i++)43         {44             t.x = s.x + d[i][0];45             t.y = s.y + d[i][1];46             t.s = s.s - 1;47             if(g[t.x][t.y] == 0)48                 q.push(t);49 50         }51     }52     while(q.size())    q.pop();53     s.x = 5;54     s.y = 5;55     q.push(s);56     while(q.size())57     {58         s = q.front();59         q.pop();60         if(s.x == 1 && s.y == 1)    break;61         for(int i = 0; i < 4; i++)62         {63             t.x = s.x + d[i][0];64             t.y = s.y + d[i][1];65             if(g[t.x][t.y] == g[s.x][s.y] + 1)66             {67                 q.push(t);68                 v.push_back(t);69                 break;70             }71         }72     }73     for(int i = v.size() - 1; i >= 0; i--)74         printf("(%d, %d)\n",v[i].x-1,v[i].y-1);75     printf("(4, 4)\n");76     return 0;77 }