广搜，之前用四个方向不标记的广搜方法错了。。记得标记四个方向，这题很纠结。。。
# include<iostream>#include <queue>using namespace std;struct Node{ int x, y; int dir; int step; int judge[4]; bool operator <(const Node t)const { return step > t.step; } }start;Node next, pre;const int Go[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int n, m, ex, ey;char map[110][110];bool visitedm[110][110][4];int ans;bool check(int x, int y){ return (x >= 0&& x < n && y >= 0 && y < m); }void Bfs(){ priority_queue <Node> Que; memset(visitedm, false, sizeof(visitedm)); start.judge[0] = 1; Que.push(start); int kkk = 0; while (!Que.empty()){ pre = Que.top(); Que.pop(); kkk ++; if (map[pre.x][pre.y] == 'T'){ ans = pre.step; return ; } for (int i = 0; i < 4; i ++){ if (i == pre.dir){ int xx = pre.x + Go[i][0]; int yy = pre.y + Go[i][1]; if (check(xx, yy) && !visitedm[xx][yy][i] && map[xx][yy] != '#'){ visitedm[xx][yy][i] = true; next.step = pre.step+1; if (map[xx][yy] == 'T'){ ans = next.step; return ; } next.x = xx, next.y = yy; next.dir = i; Que.push(next); } } else { if (pre.dir == 0 && i == 1)continue; if (pre.dir == 1 && i == 0)continue; if (pre.dir == 2 && i == 3)continue; if (pre.dir == 3 && i == 2)continue; next.x = pre.x, next.y = pre.y; next.dir = i; next.step = pre.step + 1; if (!visitedm[pre.x][pre.y][i]){ visitedm[pre.x][pre.y][i] = true; Que.push(next); } } } } }int main(){ int t; scanf("%d", &t); while (t --){ scanf("%d %d", &n, &m); for (int i = 0; i <n; i ++){ scanf("%s", map[i]); for (int j = 0; j < m; j ++){ if (map[i][j] == 'S'){ start.x = i; start.y = j; start.step = 0; start.dir = 0; memset(start.judge, 0, sizeof(start.judge)); } } } ans = -1; Bfs(); printf("%d/n", ans); } return 0; }
