Submission #828007

#	Time	Username	Problem	Language	Result	Execution time	Memory
828007		null_awe	Maze (JOI23_ho_t3)	C++14	100 / 100	642 ms	168952 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define pii pair<int, int>

vector<int> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};

int main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  int r, c, n; cin >> r >> c >> n;
  int sx, sy; cin >> sx >> sy; --sx, --sy;
  int gx, gy; cin >> gx >> gy; --gx, --gy;
  vector<string> arr(r);
  for (int i = 0; i < r; ++i) cin >> arr[i];
  // . = empty
  // # = wall
  vector<vector<bool>> vis(r, vector<bool>(c));
  vis[sx][sy] = true;
  vector<pii> q; q.push_back({sx, sy});
  queue<pii> rq; for (pii _p : q) rq.push(_p);
  while (rq.size()) {
    pii front = rq.front(); rq.pop();
    int xx = front.first, yy = front.second;
    for (int d = 0; d < 4; ++d) {
      int nx = xx + dx[d], ny = yy + dy[d];
      if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
      if (arr[nx][ny] == '#' || vis[nx][ny]) continue;
      rq.push({nx, ny});
      q.push_back({nx, ny});
      vis[nx][ny] = true;
    }
  }
  if (vis[gx][gy]) {
    cout << 0 << '\n';
    return 0;
  }
  vector<vector<pii>> dists(r, vector<pii>(c));
  for (int dist = 1;; ++dist) {
    if (!q.size()) break;
    // cout << "here" << endl;
    vector<pii> nq;
    queue<pii> rq; for (pii _p : q) rq.push(_p), dists[_p.first][_p.second] = _p;
    while (rq.size()) {
      pii front = rq.front(); rq.pop();
      int xx = front.first, yy = front.second;
      for (int d = 0; d < 4; ++d) {
        int nx = xx + dx[d], ny = yy + dy[d];
        if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
        if (vis[nx][ny] || max(abs(nx - dists[xx][yy].first), abs(ny - dists[xx][yy].second)) > n ||
            abs(nx - dists[xx][yy].first) + abs(ny - dists[xx][yy].second) == 2 * n) continue;
        vis[nx][ny] = true;
        dists[nx][ny] = dists[xx][yy];
        rq.push({nx, ny});
        nq.push_back({nx, ny});
      }
    }
    for (pii _p : nq) rq.push(_p);
    while (rq.size()) {
      pii front = rq.front(); rq.pop();
      int xx = front.first, yy = front.second;
      // cout << xx << ' ' << yy << endl;
      for (int d = 0; d < 4; ++d) {
        int nx = xx + dx[d], ny = yy + dy[d];
        if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
        if (arr[nx][ny] == '#' || vis[nx][ny]) continue;
        rq.push({nx, ny});
        nq.push_back({nx, ny});
        vis[nx][ny] = true;
      }
    }
    if (vis[gx][gy]) {
      cout << dist << '\n';
      return 0;
    }
    q = nq;
  }
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 19 / 19
• Subtask 7: 8 / 8
• Subtask 8: 6 / 6