leetcode-go/bailian/4130.saving-tang-monk/main.cc

#include <cstdio>
#include <cstring>
#include <queue>  // Use priority queue to save your time & life.

using namespace std;

const int N = 100;
const int M = 9;
const int S = 5;

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

char map[N][N + 1];
short snake[N][N];
bool flag[N][N][M + 1];

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

int main() {
  int n, m;
  while (scanf("%d %d", &n, &m) != EOF) {
    if (n == 0 && m == 0) break;
    Pos sun, tang;
    int s = 0;
    for (int i = 0; i < n; i++) {
      scanf("%s", map[i]);
      for (int j = 0; j < n; j++) {
        if (map[i][j] == 'T') {
          tang.r = i;
          tang.c = j;
          tang.key = m;
          tang.t = -1;
        } else if (map[i][j] == 'K') {
          sun.r = i;
          sun.c = j;
        } else if (map[i][j] == 'S') {
          snake[i][j] = s++;
        }
      }
    }
    priority_queue<Pos> q;
    q.push(sun);
    memset(flag, 0, sizeof(flag));
    flag[sun.r][sun.c][0] = true;
    while (!q.empty()) {
      Pos cur = q.top();
      q.pop();
      if (cur == tang) {
        tang.t = cur.t;
        break;
      }
      for (int i = 0; i < 4; i++) {
        int nx = cur.r + dx[i];
        int ny = cur.c + dy[i];
        if (nx < 0 || n <= nx || ny < 0 || n <= ny) continue;
        char grid = map[nx][ny];
        if (grid == '#') continue;
        if (grid == 'S') {
          if (flag[nx][ny][cur.key]) continue;
          if (cur.kill & (1 << snake[nx][ny]))
            q.emplace(nx, ny, cur.key, cur.kill, cur.t + 1);
          else
            q.emplace(nx, ny, cur.key, cur.kill | (1 << snake[nx][ny]),
                      cur.t + 2);
          flag[nx][ny][cur.key] = true;
        } else {
          if (!flag[nx][ny][cur.key]) {
            q.emplace(nx, ny, cur.key, cur.kill, cur.t + 1);
            flag[nx][ny][cur.key] = true;
          }
          if ('1' <= grid && grid <= '9' && grid - '0' == cur.key + 1 &&
              !flag[nx][ny][grid - '0']) {  // Get key
            q.emplace(nx, ny, grid - '0', cur.kill, cur.t + 1);
            flag[nx][ny][grid - '0'] = true;
          }
        }
      }
    }
    if (tang.t == -1)
      printf("impossible\n");
    else
      printf("%d\n", tang.t);
  }
  return 0;
}