[POJ 3984] 迷宫问题(BFS最短路径的记录和打印问题)

题目链接：http://poj.org/problem?id=3984

宽度优先搜索最短路径的记录和打印问题

 #include<iostream>

 #include<queue>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 bool maze[][];

 int go[][] = {,,,-,,,-,};

 struct node

 {

     int x,y;

     int prex,prey;

 }path[][],temp;

 void bfs()

 {

     queue<node> Q;

     node temp;

     int nx,ny;

     path[][].x=path[][].y=;

     Q.push(path[][]);

     while(!Q.empty())

     {

         temp = Q.front();

         Q.pop();

         if(temp.x==&&temp.y==)

             return;

         for(int i=;i<;i++)

         {

             nx = temp.x + go[i][];

             ny = temp.y + go[i][];

             if(nx>=&&nx<&&ny>=&&ny<&&!maze[nx][ny])

             {

                 path[nx][ny].x = nx;

                 path[nx][ny].y = ny;

                 path[nx][ny].prex = temp.x;

                 path[nx][ny].prey = temp.y;

                 maze[nx][ny] = ;

                 Q.push(path[nx][ny]);

             }

         }

     }

 }

 void print_path(int x,int y)

 {

     if(x==&&y==)

     {

         cout<<"("<<path[][].x<<", "<<path[][].y<<")"<<endl;

         return ;

     }

     int px = path[x][y].prex;

     int py = path[x][y].prey;

     print_path(px,py);

     cout<<"("<<path[x][y].x<<", "<<path[x][y].y<<")"<<endl;

 }

 int main()

 {

     for(int i=;i<;i++)

         for(int j=;j<;j++)

             scanf("%d",&maze[i][j]);

     bfs();

     print_path(,);

     return ;

 }