题目不光要求要到达终点而且要求所走的步数为5的倍数，每个时刻有三个选择，前进，左转弯，右转弯。
所以在vis数组中新增加两个维度即可，vis[x][y][dir][color]表示在(x, y)格子方向朝dir与地面接触的扇形的颜色为color，这个状态是否到达过。
1 #include <cstdio> 2 #include <queue> 3 #include <cstring> 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 Node 11 { 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<Node> 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 ", 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 ", ans); 86 else puts("destination not reachable"); 87 } 88 89 return 0; 90 }