oj.uz

Submission #828001

# Submission time Handle Problem Language Result Execution time Memory
828001 2023-08-17T01:08:06 Z null_awe Maze (JOI23_ho_t3) C++14
0 / 100
 1 ms 212 KB 
#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<int>> dists(r, vector<int>(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] = 0;
    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]) continue;
        vis[nx][ny] = true;
        dists[nx][ny] = dists[xx][yy] + 1;
        if (dists[nx][ny] <= n) 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -