leetcode-go/bailian/4115.naruto/main.cc

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

using namespace std;

const int L = 200;
const int T = 10;

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

char map[L][L + 1];
bool flag[L][L][T];

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

int m, n;

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

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