POJ 3984  bfs+回溯路径

迷宫问题

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 9218		Accepted: 5459

Description

定义一个二维数组： 

int maze[5][5] = { 	0, 1, 0, 0, 0, 	0, 1, 0, 1, 0, 	0, 0, 0, 0, 0, 	0, 1, 1, 1, 0, 	0, 0, 0, 1, 0, };

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

0 1 0 0 00 1 0 1 00 0 0 0 00 1 1 1 00 0 0 1 0

Sample Output

(0, 0)(1, 0)(2, 0)(2, 1)(2, 2)(2, 3)(2, 4)(3, 4)(4, 4) 找了到水题放松一下。。。竟然写了十几分钟。。。

/* poj3984 0ms  */#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;const int maxn=30;const int INF=(1<<28);const int N=5;bool vis[maxn][maxn];struct node{ int x,y; int dist;};node fa[maxn][maxn];int dx[]={-1,1,0,0};int dy[]={ 0,0,-1,1};bool bfs(){ queue
              
                q; q.push({ 1,1,0}); vis[1][1]=1; fa[1][1]={ 0,0}; while(!q.empty()){ node now=q.front(); q.pop(); if(now.x==5&&now.y==5) return true; for(int i=0;i<4;i++){ int nx=now.x+dx[i]; int ny=now.y+dy[i]; int nd=now.dist+1; if(vis[nx][ny]) continue; vis[nx][ny]=1; fa[nx][ny]=now; q.push({nx,ny,nd}); } } return false;}void PrintPath(){ stack
               
                 path; node now={ 5,5}; while(now.x&&now.y){ path.push(now); now=fa[now.x][now.y]; } while(!path.empty()){ printf("(%d, %d)\n",path.top().x-1,path.top().y-1); path.pop(); }}int main(){ memset(vis,1,sizeof(vis)); for(int i=1;i<=N;i++){ for(int j=1;j<=N;j++){ cin>>vis[i][j]; } } if(bfs()) PrintPath(); else printf("error\n"); return 0;}