UVa10047 The Monocycle

链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19491

（以上摘自http://blog.csdn.net/shuangde800/article/details/7686003）

【思路】

BFS。

以节点位置(x,y)方向dir底面的颜色c时间d为状态宽搜，每次只有左转、右转、向前走三个拓展。

需要注意的有初始状态为(sx,sy,0,0)，update有效简约了代码。

【代码】

 1 #include<cstdio>
 2 #include<queue>
 3 #include<vector>
 4 #include<cstring>
 5 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)
 6 using namespace std;
 7 
 8 const int maxn = 50+10;
 9 const int INF=1e9;
10 const int dx[] = {-1,0,1,0};
11 const int dy[] = {0,-1,0,1};
12 // north, west, south, east
13 struct Node{
14     int x,y,dir,c,d;
15 };
16 
17 int n,m,sx,sy,ex,ey,ans;
18 char G[maxn][maxn];
19 int vis[maxn][maxn][4][5];
20 queue<Node> q;
21 
22 void update(int x,int y,int dir,int c,int d) {
23     if(x<1 || x>n || y<1 || y>m || G[x][y]=='#') return ;
24     if(vis[x][y][dir][c]) return ;
25     vis[x][y][dir][c]=1;
26     
27     if(x==ex&&y==ey&&c==0) ans=min(ans,d);
28     q.push((Node){x,y,dir,c,d});
29 }
30 
31 void BFS() {
32     memset(vis,0,sizeof(vis));
33     
34     q.push((Node){sx,sy,0,0,0});
35     vis[sx][sy][0][0]=1;
36     while(!q.empty()) {
37         Node u=q.front(); q.pop();
38         int x=u.x,y=u.y,dir=u.dir,c=u.c,d=u.d+1;
39         update(x,y,(dir+1)%4,c,d);                  //右转 
40         update(x,y,(dir+3)%4,c,d);                  //左转 
41         update(x+dx[dir],y+dy[dir],dir,(c+1)%5,d);  //向前走 
42         if(ans<INF) return;
43     }
44 }
45 
46 int main() 
47 {
48     int kase=0;
49     while(scanf("%d%d",&n,&m)==2 && n&&m)
50     {
51         char s[maxn],c;
52         FOR(i,1,n) {
53             scanf("%s",s+1);
54             FOR(j,1,m) {
55                 c=G[i][j]=s[j];
56                 if(c=='S') sx=i,sy=j;
57                 else if(c=='T') ex=i,ey=j;
58             }
59         }
60         G[sx][sy]=G[ex][ey]='.';
61         while(!q.empty()) q.pop();
62          ans=INF;
63         BFS();
64         if(kase>0) putchar('
');
65         printf("Case #%d
",++kase);
66         if(ans==INF) printf("destination not reachable
");
67         else printf("minimum time = %d sec
",ans);
68     }
69     return 0;
70 }