注：原题为多组数据。本题输入改为只有一组数据。 【问题描述】 独轮车是一种仅有一个轮子的特殊自行车。他的轮子被等分成5个扇形，分别涂上一种不同的颜色。现在有一个人骑自行车行驶在M*N的网格平面上。每个格子的大小恰好使得当车从一个格子骑到下一个格子时，轮子恰好转过一个扇形。
如下图所示，当轮子在1号格子的中心时，蓝色扇形的外弧线中线刚好于地面接触。当它移动到下一个格子（2号格子）的时候，白色扇形的外弧线于地面接触。
有些各自中有障碍，所以车子不能通过这些格子。骑车人从某个格子出发，希望用最短的时间移动到目标格。在任何一个格子上，他要么骑到下一个格子，要么左转或者右转90度。其中每项动作恰好需要1秒来完成。初始时，他面朝北且绿色扇形贴着地面。到达目标格时，也必须是绿色扇形贴着地面，但朝向无限制。如下图所示。
【输入格式】 第一行包含两个整数M和N（1<=m,n<=100），表示迷宫的行数和列数，接下来是网格的描述，用M行长度为N的字符串来表示。字符#表示一个障碍方格，其他方格均可通行。骑车人的起点用S表示，终点用T表示。
【输出格式】 输出测试数据编号和到达目标格的最短时间（单位：秒）。如果无法到达，输出“destination not reachable”。
【输入样例】 【样例1】
1 3 S#T【样例2】
10 10 #S.......# #..#.##.## #.##.##.## .#....##.# ##.##..#.# #..#.##... #......##. ..##.##... #.###...#. #.....###T【输出样例】 【样例1】
destination not reachable【样例2】
minimum time = 49 sec【数据范围】 1<=m,n<=100
思路：使用d[x][y][dir][cor]来记录从起点到(x,y)格子，面朝dir方向，轮子颜色为cor时的最短时间。
#include<cstdio> using namespace std; const int maxn=105; const int inf=200000000; struct shu { int x,y,fang,color; }b,v; int n,m,ok=0; char a[maxn][maxn]; int d[maxn][maxn][5][5]; int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; bool vis[maxn][maxn][5][5]={0}; shu q[maxn*maxn*10*10]; void init() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%s",a[i]+1); for(int j=1;j<=m;j++) { if(a[i][j]=='S') b.x=i,b.y=j; if(a[i][j]=='T') v.x=i,v.y=j; } } } void bfs(shu t) { int root=0,frond=0; q[root++]=(shu){t.x,t.y,3,0}; vis[t.x][t.y][3][0]=1; d[t.x][t.y][3][0]=0; shu i,tt; while(root!=frond) { i=q[frond++]; //1前 tt.x=i.x+dx[i.fang]; tt.y=i.y+dy[i.fang]; tt.fang=i.fang; tt.color=(i.color+1)%5; if(a[tt.x][tt.y]!='#') if(tt.x<=n&&tt.x>=1&&tt.y<=m&&tt.y>=1) if(vis[tt.x][tt.y][tt.fang][tt.color]==0) { q[root++]=tt; d[tt.x][tt.y][tt.fang][tt.color]=d[i.x][i.y][i.fang][i.color]+1; vis[tt.x][tt.y][tt.fang][tt.color]=1; if(tt.x==v.x&&tt.y==v.y&&tt.color==0) { printf("minimum time = %d sec\n",d[tt.x][tt.y][tt.fang][tt.color]); ok=1; return; } } //2右 tt=i; tt.fang=(i.fang+1)%4; if(vis[tt.x][tt.y][tt.fang][tt.color]==0) { q[root++]=tt; d[tt.x][tt.y][tt.fang][tt.color]=d[i.x][i.y][i.fang][i.color]+1; vis[tt.x][tt.y][tt.fang][tt.color]=1; } //3左 tt=i; tt.fang=(i.fang+3)%4; if(vis[tt.x][tt.y][tt.fang][tt.color]==0) { q[root++]=tt; d[tt.x][tt.y][tt.fang][tt.color]=d[i.x][i.y][i.fang][i.color]+1; vis[tt.x][tt.y][tt.fang][tt.color]=1; } } } int main() { //freopen("monocycle.in","r",stdin); //freopen("monocycle.out","w",stdout); init(); bfs(b); if(!ok) printf("destination not reachable\n"); return 0; }