1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cctype> 5 #include <cmath> 6 #include <time.h> 7 #include <string> 8 #include <map> 9 #include <stack>10 #include <set>11 #include <queue>12 #include <vector>13 #include <algorithm>14 #include <iostream>15 using namespace std;16 typedef long long ll;17 #define PI acos( -1.0 )18 typedef pair<int, int> P;19 const double E = 1e-8;20 const int NO = 100 + 5;21 int a[10][10], dx[10][10], dy[10][10];22 int mark[10][10];23 int dir[][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };24 25 void output( int x, int y )26 {27     if( x == 0 && y == 0 )28     {29         printf( "(0, 0)\n" );30         return;31     }32     output( dx[x][y], dy[x][y] );33     printf( "(%d, %d)\n", x, y );34 }35 36 void bfs()37 {38     queue <P> q;39     memset( mark, 0, sizeof( mark ) );40     memset( dx, 0, sizeof( dx ) );41     memset( dy, 0, sizeof( dy ) );42     q.push( P( 0, 0 ) );43     dx[0][0] = dy[0][0] = -1;44     while( !q.empty() )45     {46         P t = q.front(); q.pop();47         if( t.first == 4 && t.second == 4 )48         {49             output( 4, 4 );50             return;51         }52         for( int i = 0; i < 5; ++i )53         {54             int xx = dir[i][0] + t.first;55             int yy = dir[i][1] + t.second;56             if( xx >= 0 && xx < 5 && yy >= 0 && yy < 5 && !mark[xx][yy] && a[xx][yy] == 0 )57             {58                 mark[xx][yy] = 1;59                 dx[xx][yy] = t.first;60                 dy[xx][yy] = t.second;61                 q.push( P( xx, yy ) );62             }63         }64     }65 }66 67 int main()68 {69     for( int i = 0; i < 5; ++i )70         for( int j = 0; j < 5;++j )71             scanf( "%d", &a[i][j] );72     bfs();73     return 0;74 }