題目大意：
獨輪車的車輪被分為5個扇形，分別塗上一種不同的顏色，現在有一個人行駛在M*N的玩個平面上。每個格子的大小剛好為一個扇形。有些格子有障礙，騎車的人從S出發要到達T，途中，在任何一個格子的時候他要麼騎到下一個格子，要麼左轉或者右轉90度，初始他面朝北，並且綠色格子貼著地面，要求到終點時候也是綠色格子貼著地面。
思路：
半年前覺得挺難的題目現在看起來好簡單。哈哈哈哈哈哈哈哈哈~
BFS。。
狀態需要記錄方向和此時的顏色。
代碼略丑。主要是BFS過程中我是直接枚舉的。
#include#include #include using namespace std; const int MAXN=30; char map[MAXN][MAXN]; bool vis[MAXN][MAXN][5][4];//x,y,color,dir int m,n; struct state { int x,y; int step; int dir;//direction :north:0 south:1 east:2 west:3 int color;//開始為0，終點也要為0 bool operator <(const state &a)const { return step > a.step; } state(){;} state(int x,int y,int step,int dir,int color) :x(x) ,y(y),step(step), dir(dir), color(color){} }start,fin; int bfs() { memset(vis,0,sizeof(vis)); priority_queue q; q.push(start); vis[start.x][start.y][start.color][start.dir]=true; while(!q.empty()) { state cur=q.top(); q.pop(); if(cur.x==fin.x && cur.y==fin.y && cur.color==0)//找到答案了！ return cur.step; int x=cur.x,y=cur.y,step=cur.step,color=cur.color,dir=cur.dir; switch(cur.dir) { case 0: //北 if(!vis[x-1][y][(color+1) % 5][dir] && map[x-1][y]!='#') { vis[x-1][y][(color+1) % 5][dir]=1; q.push(state(x-1,y,step+1,dir,(color+1) % 5)); } if(!vis[x][y][color][2]){ vis[x][y][color][2]=1; q.push(state(x,y,step+1,2,color)); } if(!vis[x][y][color][3]) { vis[x][y][color][3]=1; q.push(state(x,y,step+1,3,color)); } break; case 1: //南 if(!vis[x+1][y][(color+1) % 5][dir] && map[x+1][y]!='#') { vis[x+1][y][(color+1) % 5][dir]=1; q.push(state(x+1,y,step+1,dir,(color+1) % 5)); } if(!vis[x][y][color][2]){ vis[x][y][color][2]=1; q.push(state(x,y,step+1,2,color)); } if(!vis[x][y][color][3]) { vis[x][y][color][3]=1; q.push(state(x,y,step+1,3,color)); } break; case 2: //東 if(!vis[x][y+1][(color+1) % 5][dir] && map[x][y+1]!='#') { vis[x][y+1][(color+1) % 5][dir] =1; q.push(state(x,y+1,step+1,dir,(color+1) % 5)); } if(!vis[x][y][color][0]){ vis[x][y][color][0]=1; q.push(state(x,y,step+1,0,color)); } if(!vis[x][y][color][1]){ vis[x][y][color][1]=1; q.push(state(x,y,step+1,1,color)); } break; case 3: //西 if(!vis[x][y-1][(color+1) % 5][dir] && map[x][y-1]!='#') { vis[x][y-1][(color+1) % 5][dir]=1; q.push(state(x,y-1,step+1,dir,(color+1) % 5)); } if(!vis[x][y][color][0]){ vis[x][y][color][0]=1; q.push(state(x,y,step+1,0,color)); } if(!vis[x][y][color][1]){ vis[x][y][color][1]=1; q.push(state(x,y,step+1,1,color)); } break; } } return -1; } int main() { int kase=1; while(~scanf(%d%d,&m,&n),m||n) { for(int i=1;i<=m;i++) scanf(%s,map[i]+1); for(int i=0;i<=n+1;i++) //最外面加上一層圍牆，等下過程就可以減少判斷。 map[0][i]=map[m+1][i]='#'; for(int i=0;i<=m+1;i++) map[i][0]=map[i][n+1]='#'; /* for(int i=0;i<=m+1;i++) { for(int j=0;j<=n+1;j++) printf(%c,map[i][j]); puts(); } */ for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(map[i][j]=='S') { state temp(i,j,0,0,0); start=temp; map[i][j]='.'; } else if(map[i][j]=='T') { state temp(i,j,0,0,0); fin=temp; map[i][j]='.'; } } } int ans=bfs(); if(kase!=1) printf( ); printf(Case #%d ,kase++); if(ans==-1) printf(destination not reachable ); else printf(minimum time = %d sec ,ans); } return 0; }
