[USACODec2020G]Replication

The first line contains two space-separated integers N and D. The next N lines of input each contain N characters. Each character is one of '.', 'S', or '#'. '.' and 'S' both represent empty cells, with 'S' denoting a possible starting position for the robot. '#' denotes a rock.
All characters in the first and last row and first and last column are '#'.

C++ 解法, 执行用时: 157ms, 内存消耗: 29588K, 提交时间: 2022-01-01 19:36:28

// USACO 2020 Dec G. Replication
#include <bits/stdc++.h>
#define _all(i, a, b) for (int i = (a); i <= (int)(b); ++i)
using namespace std;
struct Stat {
  int x, y, d;
  bool operator<(const Stat &Y) const { return d < Y.d; }
};
typedef vector<int> VI;
const int DX[] = {1, -1, 0, 0}, DY[] = {0, 0, 1, -1};
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int N, D;
  string line;
  cin >> N >> D;
  vector<VI> D0(N + 1, VI(N + 1, -1)),
      D1 = D0, G(N + 1, VI(N + 1));  // G[x,y]: 能进复制机器人吗?
  queue<Stat> q0, q1;
  _all(i, 1, N) {
    cin >> line;
    _all(j, 1, N) {
      char c = line[j - 1];
      if (c == '#') G[i][j] = 1, q0.push({i, j, 0}), D0[i][j] = 0;
      if (c == 'S') G[i][j] = 1, q1.push({i, j, 0}), D1[i][j] = 0;
    }
  }
  Stat s;
  while (!q0.empty()) {  // 计算(x,y)到石头的最短距离D0(x,y)
    s = q0.front(), q0.pop();
    _all(i, 0, 3) {
      int x = s.x + DX[i], y = s.y + DY[i], &d = D0[x][y];
      if (x >= 1 && y >= 1 && x <= N && y <= N && d < 0)
        d = s.d + 1, q0.push({x, y, s.d + 1});
    }
  }
  while (!q1.empty()) {
    s = q1.front(), q1.pop();  // 本体可能在D1[x,y]时刻到(x,y)
    if (s.d / D >= D0[s.x][s.y]) continue;  // 它的copy要碰石头
    _all(i, 0, 3) {
      int x = s.x + DX[i], y = s.y + DY[i], &d = D1[x][y];
      if (d < 0 && s.d / D < D0[x][y] && !G[x][y])
        d = s.d + 1, q1.push({x, y, s.d + 1});
    }
  }
  vector<VI> InQ(N + 1, VI(N + 1));
  priority_queue<Stat> pq;  // 从本体所有可能位置扩展，起点D值不同所以不能用BFS
  int cnt = 0;
  _all(x, 1, N) _all(y, 1, N) if (D1[x][y] >= 0) {
    // 本体能在D1[x,y]走到(x,y)且其复制体不碰石头，能往外扩展几步?
    pq.push({x, y, D0[x][y] - 1}), InQ[x][y] = 1, ++cnt;
  }
  while (!pq.empty()) {
    s = pq.top(), pq.pop();
    if (s.d == 0) continue;
    _all(i, 0, 3) {
      int nx = s.x + DX[i], ny = s.y + DY[i];
      if (!InQ[nx][ny] && !G[nx][ny])
        InQ[nx][ny] = 1, pq.push({nx, ny, s.d - 1}), ++cnt;
    }
  }
  cout << cnt << endl;
  return 0;
}
// Accepted 100 [USACO20DEC G] Replication 1.45s 29.95MB 1.98KB C++11

详情