1 #include<iostream> 2 #include<string.h> 3 #include<queue> 4  5 using namespace std; 6  7 int map[5][5]; 8 int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; 9 int visit[5][5]={0};10 int last[25];11 int ans[25];//用last得到的最短路径是倒置的，通过last再倒回来；12 13 struct Node{14     int x,y;15     int logo;16 }node[25];17 18 int main()19 {20     for(int i=0;i<5;i++)21     {22         for(int j=0;j<5;j++)23         {24             cin>>map[i][j];25             node[5*i+j].x=i;26             node[5*i+j].y=j;27             node[5*i+j].logo=map[i][j];28         }29     }30 31     queue<Node> Q;32 33     Q.push(node[0]);34 35     while(!Q.empty()){36         Node a=Q.front();37         visit[a.x][a.y]=1;38         //cout<<a.x<<‘\t‘<<a.y<<endl;39         Q.pop();40         for(int i=0;i<4;i++)41         {42             Node next;43             next.x=a.x+dir[i][0];44             next.y=a.y+dir[i][1];45             next.logo=node[5*next.x+next.y].logo;46             if(next.x>=0&&next.x<5&&next.y>=0&&next.y<5&&next.logo==0&&visit[next.x][next.y]==0)47             {48                 Q.push(next);49                 last[next.x*5+next.y]=a.x*5+a.y;//last得到上一个节点的位置所在50             }51         }52     }53 54     int p=24,top=0;55     while(true)56     {57         ans[top++]=p;58         if(p==0) break;59         p=last[p];60     }61 62     while(top>0)63     {64         --top;65          cout<<"("<<ans[top]/5<<", "<<ans[top]%5<<")"<<endl;66     }67 68     return 0;69 }