这道题稍微有点烦，主要是确定状态，除了表示位置（x,y）之外。还要记录当前方向朝地板的颜色，最后我们还需要记录步骤数。在确立状态后就是编码了。
我写的代码有点冗长。献丑了。
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <cstdlib> 6 #include <algorithm> 7 #include <vector> 8 #include <queue> 9 #include <stack> 10 #define LEN 100 11 #define INF 0x7fffffff 12 13 using namespace std; 14 15 char Map[LEN][LEN]; 16 int n, m, cnt = 1, vis[LEN][LEN][10][10]; 17 int xx[] = {-1, 0, 1, 0}; //初始向上(dir+1)%4右转(dir-1)%4左转 18 int yy[] = { 0, 1, 0,-1}; 19 typedef struct { 20 int x, y, dir, col, step; 21 }POINT; 22 23 int BFS() 24 { 25 queue<POINT> q; 26 memset(vis, 0, sizeof vis); 27 for(int i=1; i<=n; i++){ 28 for(int j=1; j<=m; j++){ 29 if(Map[i][j] == 'S'){ 30 POINT vex;vex.x = i;vex.y = j; 31 vex.step = 1;vex.col = 0; 32 vex.dir = 0; 33 vis[vex.x][vex.y][vex.dir][vex.col] = 1; 34 q.push(vex); 35 break; 36 } 37 } 38 } 39 while(!q.empty()){ 40 POINT vex = q.front();q.pop(); 41 if(Map[vex.x][vex.y] == 'T' && vex.col == 0) return vex.step-1; 42 POINT newv;newv.x = vex.x;newv.y = vex.y; 43 newv.step = vex.step+1;newv.col = vex.col; 44 newv.dir = (vex.dir+1)%4; 45 if(vis[newv.x][newv.y][newv.dir][newv.col] == 0){ 46 vis[newv.x][newv.y][newv.dir][newv.col] = 1; 47 q.push(newv); 48 } 49 newv.dir = (vex.dir-1+4)%4; 50 if(vis[newv.x][newv.y][newv.dir][newv.col] == 0){ 51 vis[newv.x][newv.y][newv.dir][newv.col] = 1; 52 q.push(newv); 53 } 54 newv.col = (vex.col+1)%5;newv.dir = vex.dir; 55 newv.x = vex.x+xx[newv.dir];newv.y = vex.y+yy[newv.dir]; 56 if(newv.x>=1 && newv.x<=n && newv.y>=1 && newv.y<=m && Map[newv.x][newv.y] != '#' && vis[newv.x][newv.y][newv.dir][newv.col] == 0){ 57 vis[newv.x][newv.y][newv.dir][newv.col] = 1; 58 q.push(newv); 59 } 60 } 61 return -1; 62 } 63 64 int main() 65 { 66 // freopen("in.txt", "r", stdin); 67 68 while(scanf("%d%d", &n, &m)!=EOF) 69 { 70 memset(Map, 0, sizeof Map); 71 if(n==0 && m==0)break; 72 getchar(); 73 for(int i=1; i<=n; i++){ 74 for(int j=1; j<=m; j++){ 75 scanf("%c", &Map[i][j]); 76 77 } 78 getchar(); 79 } 80 int ans = BFS(); 81 if(cnt!=1)printf(" "); 82 printf("Case #%d ", cnt++); 83 if(ans == -1)printf("destination not reachable "); 84 else printf("minimum time = %d sec ", ans); 85 } 86 return 0; 87 }