这道题定义状态的时候需要多考虑，我用了四重数组，后面2维表示的分别是方向和颜色，同时旋转的时候对4取模时候如果是减一那么就加三mod 4,于是很简单了，就是输出极其恶心，不想吐槽了。。。
#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;struct Node{ int x, y, d, c, t; Node() {} Node(int _x, int _y, int _d, int _c, int _t):x(_x), y(_y), d(_d), c(_c), t(_t) {}};int vis[30][30][10][10], m, n, ans;char maze[30][30];bool judge(int x, int y){ if(x < 0 || x >= n || y < 0 || y >= m || maze[x][y] == '#') return false; return true;}void bfs(int i, int j){ memset(vis, 0, sizeof(vis)); vis[i][j][0][0] = 1; queue <Node> que; que.push(Node(i, j, 0, 0, 0)); while(!que.empty()){ Node temp = que.front(); que.pop(); if(maze[temp.x][temp.y] == 'T' && temp.c == 0){ ans = temp.t; return ; } if(!vis[temp.x][temp.y][(temp.d+1)%4][temp.c]){ que.push(Node(temp.x, temp.y, (temp.d+1)%4, temp.c, temp.t+1)); vis[temp.x][temp.y][(temp.d+1)%4][temp.c] = 1; } if(!vis[temp.x][temp.y][(temp.d+3)%4][temp.c]){ que.push(Node(temp.x, temp.y, (temp.d+3)%4, temp.c, temp.t+1)); vis[temp.x][temp.y][(temp.d+3)%4][temp.c] = 1; } if(temp.d == 0){ if(judge(temp.x-1, temp.y) && !vis[temp.x-1][temp.y][temp.d][(temp.c+1)%5]){ que.push(Node(temp.x-1, temp.y, temp.d, (temp.c+1)%5, temp.t+1)); vis[temp.x-1][temp.y][temp.d][(temp.c+1)%5] = 1; } } else if(temp.d == 1){ if(judge(temp.x, temp.y+1) && !vis[temp.x][temp.y+1][temp.d][(temp.c+1)%5]){ que.push(Node(temp.x, temp.y+1, temp.d, (temp.c+1)%5, temp.t+1)); vis[temp.x][temp.y+1][temp.d][(temp.c+1)%5] = 1; } } else if(temp.d == 2){ if(judge(temp.x+1, temp.y) && !vis[temp.x+1][temp.y][temp.d][(temp.c+1)%5]){ que.push(Node(temp.x+1, temp.y, temp.d, (temp.c+1)%5, temp.t+1)); vis[temp.x+1][temp.y][temp.d][(temp.c+1)%5] = 1; } } else{ if(judge(temp.x, temp.y-1) && !vis[temp.x][temp.y-1][temp.d][(temp.c+1)%5]){ que.push(Node(temp.x, temp.y-1, temp.d, (temp.c+1)%5, temp.t+1)); vis[temp.x][temp.y-1][temp.d][(temp.c+1)%5] = 1; } } }}int main(){ int kase = 0; while(scanf("%d%d", &n, &m) != EOF && n && m){ for(int i = 0; i < n; i++) scanf("%s", maze[i]); ans = -1; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if(maze[i][j] == 'S') bfs(i, j); kase++; if(kase > 1) PRintf("/n"); printf("Case #%d/n", kase); if(ans == -1) printf("destination not reachable/n"); else printf("minimum time = %d sec/n", ans); } return 0;}新闻热点
疑难解答
