首页 > 代码库 > UVA 816 Abbott’s Revenge

UVA 816 Abbott’s Revenge

2024-07-12 21:50:38   223人阅读

bfs求最短路，递归打印最短路的具体路径；

难点：

　　当前状态和转弯方式很复杂，要仔细处理；

　　递归打印：用一个数组存储路径中结点的前一个节点，递归查找 （bfs无法确定下一个结点，但对于没一个结点，它的上一个结点是确定的！）

 

 

ps：输出因为太懒不想处理所以按书上打的；递归打印理解有点麻烦。。。

  1 #include <iostream>  2 #include <cstring>  3 #include <algorithm>  4 #include <queue>  5 #include <vector>  6 #include <cstdio>  7 using namespace std;  8   9 struct node { 10     int x,y; 11     int w; 12     void init (int nx,int ny,int nw){ 13         x=nx; 14         y=ny; 15         w=nw; 16     } 17 }p[10][10][5]; 18  19 int visit[10][10][5]; 20 int map[10][10][4]; 21 int dir[4][3][2]={{-1,0,0,-1,0,1}, 22                   {0,1,-1,0,1,0}, 23                   {1,0,0,1,0,-1}, 24                   {0,-1,1,0,-1,0} 25                   }; 26  27 int id (char c){ 28     if (c==‘N‘||c==‘F‘) 29         return 0; 30     else if (c==‘E‘||c==‘L‘) 31         return 1; 32     else if (c==‘S‘||c==‘R‘) 33         return 2; 34     else return 3; 35 } 36 node ans[1000]; 37 int tot; 38 int x0,y0,x1,y1,w1,sx,sy; 39  40 void print (int x,int y,int w); 41  42 int bfs (int x,int y,int w){ 43     queue<node> q; 44     while (!q.empty ()) 45         q.pop (); 46     node a,b; 47     a.init (x,y,w); 48     visit[a.x][a.y][a.w]=0; 49     q.push (a); 50     while (!q.empty ()){ 51         a=q.front ();//cout<<a.x<<" "<<a.y<<" "<<a.w<<endl; 52         q.pop (); 53         if (a.x==sx&&a.y==sy){ 54             print (a.x,a.y,a.w); 55             return 1; 56         } 57         int xx,yy,ww; 58         for (int i=0;i<3;i++){ 59             xx=a.x;yy=a.y;ww=a.w; 60             xx+=dir[a.w][i][0]; 61             yy+=dir[a.w][i][1]; 62             if (i==1) 63                 ww=(ww+3)%4; 64             else if (i==2) 65                 ww=(ww+1)%4; 66             b.init (xx,yy,ww); 67             if ((map[a.x][a.y][a.w]&(1<<i))){ 68                 if (xx<1||xx>9||yy<1||yy>9) 69                     continue ; 70                 if (visit[xx][yy][ww]>=0) 71                     continue ; 72                 visit[xx][yy][ww]=visit[a.x][a.y][a.w]+1; 73                 p[xx][yy][ww]=a;　　　　//存储路径中的父结点 74                 q.push (b); 75             } 76  77         } 78     } 79     return 0; 80 } 81  82 void print (int x,int y,int w){ 83     vector<node> v; 84     node a,b; 85     a.init (x,y,w); 86     v.push_back (a); 87     while (visit[a.x][a.y][a.w]){ 88         a=p[a.x][a.y][a.w]; 89         v.push_back (a); 90     } 91     a.init (x0,y0,w1); 92     v.push_back (a); 93  94     int cnt=0; 95     for (int i=v.size()-1;i>=0;i--){ 96         if (cnt%10==0) cout<<" "; 97         cout<<" ("<<v[i].x<<","<<v[i].y<<")"; 98         if (++cnt%10==0) cout<<endl; 99     }100     if (v.size()%10!=0) cout<<endl;101 }102 103 int main (){104     char s[30];105     while (cin>>s){106         if (strcmp (s,"END")==0)107             break ;108         tot=0;109         memset (map,0,sizeof map);110         memset (visit,-1,sizeof visit);111         cout<<s<<endl;112         char c;113         cin>>x1>>y1>>c>>sx>>sy;114         x0=x1;y0=y1;115         w1=id (c);116         x1+=dir[w1][0][0];117         y1+=dir[w1][0][1];118         int xx,yy;119         while (cin>>xx&&xx){120             cin>>yy;121             gets (s);122             int i=1;123             int j=id (s[1]);124             while (s[i++]!=‘*‘){//cout<<i<<" "<<s[i];125                 if (s[i]==‘ ‘){126                     j=id (s[++i]);127                     continue ;128                 }129                 map[xx][yy][j]^=(1<<id (s[i]));130             }131             //for (j=0;j<4;j++)132             //    cout<<map[xx][yy][j]<<endl;133         }//cout<<xx<<endl;134         if (!bfs (x1,y1,w1))135             cout<<"  No Solution Possible"<<endl;136     }137     return 0;138 }


联系
我们