2 #include<queue>
  3 #include<stack>
  4 using namespace std;
  5 //===================================================================
  6 int maze[5][5];
  7 bool mark[5][5];
  8 struct Point 
  9 {
 10     int x,y;
 11 };
 12 
 13 int dir[4][2]={0,1,0,-1,1,0,-1,0};
 14 Point dis[5][5];
 15 stack<Point> S;
 16 int map[5][5];//第三种记录方法
 17 //=====================================================================
 18 
 19 bool InMap(int i,int j)
 20 {
 21     if(i>=0&& i<=4 && j>=0 && j<=4) return true;
 22     else return  false;
 23 }
 24 
 25 void func(int i, int j)
 26 {
 27     if(i==0 && j==0)
 28     {
 29          printf("(0, 0)\n");
 30          return ;
 31     }
 32     Point t;
 33     t.x=i;
 34     t.y=j;
 35     S.push(t);
 36     func(dis[i][j].x,dis[i][j].y);    //递归放入栈，不知道怎么倒序输出
 37 
 38 }
 39 
 40 /*方法二===================================================*/
 41 //void dfs(int x,int y)
 42 //{
 43 //    int pre_x=dis[x][y].x;
 44 //    int pre_y=dis[x][y].y;
 45 //    //如果有祖先，则搜索祖先
 46 //    if(pre_x!=-1 && pre_y!=-1)
 47 //        dfs(pre_x,pre_y);
 48 //    //输出自己的地址，无论是否有祖先(队列中无祖先的只有【0】【0】点）
 49 //    printf("(%d, %d)\n",x,y);
 50 //}
 51 
 52 /*方法三===================================================*/
 53 //void print(int i,int j)
 54 //{
 55 //   if(i==0 && j==0)
 56 //   {
 57 //       printf("(0, 0)\n");
 58 //       return ;
 59 //   }
 60 //
 61 //   print(map[i][j]/5,map[i][j]%5);//先遍历祖先
 62 //   printf("(%d, %d)\n",i,j);
 63 //}
 64 
 65 /*方法四===================================================*/
 66 void print(int i,int j)
 67 {
 68    if(i==0 && j==0)
 69    {
 70        printf("(0, 0)\n");
 71        return ;
 72    }
 73 
 74    print(dis[i][j].x,dis[i][j].y);//先遍历祖先,这两句话的位置很重要，先到祖先，在写自己（下一句话），第一次的错误就是两句话反了
 75     //导致顺序颠倒了
 76    printf("(%d, %d)\n",i,j); 
 77 }
 78 
 79 
 80 void BFS()
 81 {
 82     queue<Point> Q;
 83 
 84     Point cur,m,q;
 85     cur.x=0;
 86     cur.y=0;
 87     mark[0][0]=1;
 88     Q.push(cur);
 89     dis[0][0].x=0;
 90     dis[0][0].y=0;
 91     int xt,yt;
 92 
 93     while(!Q.empty())
 94     {
 95         m=Q.front();
 96         Q.pop();
 97 
 98         for(int i=0;i<4;i++)
 99         {
100             xt=m.x+dir[i][0];
101             yt=m.y+dir[i][1];
102             if(xt==4 && yt==4) 
103             {
104                // func(m.x,m.y);//方法一：放入栈
105                 //dfs(m.x,m.y);//方法二：用深搜
106                 //map[xt][yt]=m.x*5+m.y;//方法三： 用横竖法（自己起的名字），来记录上一次的位置
107                 dis[4][4].x=m.x;
108                 dis[4][4].y=m.y;
109                 print(4,4);
110                 return ;
111             }
112             if(InMap(xt,yt) && mark[xt][yt]==0 && maze[xt][yt]==0)//判断下面一层的结点是否符合
113             {
114 
115                 dis[xt][yt].x=m.x;//记录每上次的结点，这样才可以把整个拎起来
116                 dis[xt][yt].y=m.y;//用dis[][]点来记录每个节点的父节点，因为遍历过就会mark=1,所以只会有一个父节，不会被覆盖
117 
118                 //map[xt][yt]=m.x*5+m.y;//记录路径的好方法！！记录前驱
119 
120                 mark[xt][yt]=1;//访问过后
121                 q.x=xt;
122                 q.y=yt;
123                 Q.push(q);
124 
125             }
126         }
127     }
128 }
129 
130 
131 
132 int main()
133 {
134     int i,j;
135 
136     freopen("in.txt","r",stdin);
137     for(i=0;i<5;i++)
138         for(j=0;j<5;j++)
139             scanf("%d",&maze[i][j]);
140 
141     BFS();
142 
143     //print(4,4);
144     //while(!S.empty())//打印路径
145     //{
146     //    printf("(%d, %d)\n",S.top().x,S.top().y);
147     //    S.pop();
148     //}
149     //printf("(4, 4)\n");
150 
151 
152 
153 
154 
155 
156 }