leetcode-go/bailian/4116.rescue-operations/main.cc

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int L = 200;

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

int s, n, m;

int flag[L][L];

char map[L][L + 1];

struct Pos {
  int r;
  int c;
  bool k;
  int t;
  Pos(int r = 0, int c = 0, bool k = false, int t = 0)
      : r(r), c(c), k(k), t(t){};
  bool operator==(const Pos that) const {
    return this->r == that.r && this->c == that.c;
  }
};

bool is_expandable(int x, int y) {
  if (x < 0 || n <= x || y < 0 || m <= y) return false;
  if (map[x][y] == '#' || (flag[x][y] & 1) != 0) return false;
  return true;
}

int main() {
  scanf("%d", &s);
  while (s--) {
    scanf("%d %d", &n, &m);
    Pos r, a;
    for (int i = 0; i < n; i++) {
      scanf("%s", map[i]);
      for (int j = 0; j < m; j++) {
        if (map[i][j] == 'a') {
          a.r = i;
          a.c = j;
          a.t = -1;
        } else if (map[i][j] == 'r') {
          r.r = i;
          r.c = j;
        }
      }
    }
    queue<Pos> q;
    q.push(r);
    memset(flag, 0, sizeof(flag));
    flag[r.r][r.c] |= 1;
    while (!q.empty()) {
      Pos &cur = q.front();
      q.pop();
      if (cur == a) {
        a.t = cur.t;
        break;
      }
      if (cur.k == true) {
        for (int i = 0; i < 4; i++) {
          int nx = cur.r + dx[i];
          int ny = cur.c + dy[i];
          if (!is_expandable(nx, ny)) continue;
          q.push(Pos(nx, ny, false, cur.t + 1));
          flag[nx][ny] |= 1;
        }
      } else if (map[cur.r][cur.c] == 'x') {
        if ((flag[cur.r][cur.c] & 2) == 0) {
          q.push(Pos(cur.r, cur.c, true, cur.t + 1));
          flag[cur.r][cur.c] |= 2;
        }
      } else {
        for (int i = 0; i < 4; i++) {
          int nx = cur.r + dx[i];
          int ny = cur.c + dy[i];
          if (!is_expandable(nx, ny)) continue;
          q.push(Pos(nx, ny, false, cur.t + 1));
          flag[nx][ny] |= 1;
        }
      }
    }
    if (a.t == -1)
      printf("Impossible\n");
    else
      printf("%d\n", a.t);
  }
  return 0;
}