题目不光要求要到达终点而且要求所走的步数为5的倍数，每个时刻有三个选择，前进，左转弯，右转弯。
所以在vis数组中新增加两个维度即可，vis[x][y][dir][color]表示在(x, y)格子方向朝dir与地面接触的扇形的颜色为color，这个状态是否到达过。
1 #include2 #include 3 #include 4 using namespace std; 5 6 const int maxn = 30; 7 char maze[maxn][maxn]; 8 bool vis[maxn][maxn][4][5]; 9 10 struct Node11 {12 int x, y, d, t, step;13 Node(int x=0, int y=0, int d=0, int t=0, int step=0):x(x), y(y), d(d), t(t), step(step) {}14 }st, ed;15 16 int dx[] = { -1, 0, 1, 0 };17 int dy[] = { 0, 1, 0, -1 };18 19 int row, col;20 21 inline bool in(int x, int y)22 { return x >= 0 && x < row && y >= 0 && y < col; }23 24 int BFS()25 {26 memset(vis, false, sizeof(vis));27 queue Q;28 Q.push(st);29 vis[st.x][st.y][0][0] = true;30 while(!Q.empty())31 {32 Node now = Q.front(); Q.pop();33 if(now.x == ed.x && now.y == ed.y && now.step % 5 == 0)34 return now.t;35 36 int d = now.d;37 int x = now.x + dx[d];38 int y = now.y + dy[d];39 int t = now.t + 1;40 int step = now.step + 1;41 if(in(x, y) && maze[x][y] != '#' && !vis[x][y][d][step%5])42 {43 Q.push(Node(x, y, d, t, step));44 vis[x][y][d][step%5] = true;45 }46 47 for(int i = 1; i <= 3; i += 2)48 {49 x = now.x; y = now.y;50 d = (now.d + i) % 4;51 t = now.t + 1;52 step = now.step;53 if(!vis[x][y][d][step%5])54 {55 Q.push(Node(x, y, d, t, step));56 vis[x][y][d][step%5] = true;57 }58 }59 }60 return -1;61 }62 63 int main()64 {65 //freopen("in.txt", "r", stdin);66 67 int kase = 0;68 while(scanf("%d%d", &row, &col) == 2)69 {70 if(row == 0 && col == 0) break;71 72 if(kase++ > 0) puts("");73 printf("Case #%d\n", kase);74 75 if(row == 0 && col == 0) break;76 for(int i = 0; i < row; i++) scanf("%s", maze[i]);77 for(int i = 0; i < row; i++)78 for(int j = 0; j < col; j++)79 {80 if(maze[i][j] == 'S') st = Node(i, j, 0, 0, 0);81 if(maze[i][j] == 'T') ed = Node(i, j);82 }83 84 int ans = BFS();85 if(ans >= 0) printf("minimum time = %d sec\n", ans);86 else puts("destination not reachable");87 }88 89 return 0;90 }