queen.cc

#include <cstdio>
#include <bits/stl_algobase.h>
#define MAXN 1005

using std::min;

const int INF = 1<<30, MASK = (1 << 10) - 1, START = MAXN*MAXN*4;
int n, m;
char S[MAXN][MAXN];
int D[MAXN][MAXN][4];
int xi, yi, xf, yf;

int Q[2][MAXN*MAXN*4];
inline int codify(int x, int y, int d) {
  return x | (y << 10) | (d << 20);
}

inline bool valid(int x, int y) {
  return x >= 0 and x < n and y >= 0 and y < m and S[x][y] != 'X';
}

int dx[][2] = {{-1, 1}, {0, 0}, {-1, 1}, {-1, 1}},
    dy[][2] = {{-1, 1}, {-1, 1}, {1, -1}, {0, 0}};

void bfs() {
  int start = START, end = START;
  for (int i = 0; i < 4; i++) {
    Q[end++] = codify(xi, yi, i);
    D[xi][yi][i] = 1;
  }
  int du, x, y, ux, uy, ud, tmp;
  while (start < end) {
    tmp = Q[start++];
    ux = tmp & MASK; uy = (tmp >> 10) & MASK; ud = (tmp >> 20);
    if (ux == xf and uy == yf)
      return;
    du = D[ux][uy][ud];
    for (int i = 0; i < 2; i++) {
      x = ux + dx[ud][i], y = uy + dy[ud][i];
      if (valid(x, y) and D[x][y][ud] > du) {
        Q[--start] = codify(x, y, ud);
        D[x][y][ud] = du;
      }
    }
    for (int d = 0; d < 4; d++) {
      if (D[ux][uy][d] > du + 1) {
        Q[end++] = codify(ux, uy, d);
        D[ux][uy][d] = du + 1;
      }
    }
  }
}

int main() {
  int tc;
  scanf("%d", &tc);
  while (tc--) {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
      scanf("%s", S[i]);
      for (int j = 0; j < m; j++) {
        if (S[i][j] == 'S')
          xi = i, yi = j;
        else if (S[i][j] == 'F') {
          xf = i, yf = j;
        }
      }
    }
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
        for (int k = 0; k < 4; k++)
          D[i][j][k] = INF;
    bfs();
    int ans = INF;
    for (int i = 0; i < 4; i++)
      ans = min(ans, D[xf][yf][i]);
    printf("%d\n", ans < INF ? ans : -1);
  }
}