Submission #1214825

#TimeUsernameProblemLanguageResultExecution timeMemory
1214825mdn2002Maze (JOI23_ho_t3)C++20
8 / 100
229 ms96252 KiB
/*
Mayoeba Yabureru
*/
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

void solve() {
  int r, c, n, sx, sy, fx, fy;
  cin >> r >> c >> n >> sx >> sy >> fx >> fy;

  vector a(r + 1, vector(c + 1, ' '));
  for (int i = 1; i <= r; i ++) {
    for (int j = 1; j <= c; j ++) cin >> a[i][j];
  }

  queue<vector<int>> last;
  vector dis(r + 1, vector(c + 1, 100000000)), diss = dis;
  dis[sx][sy] = 0;
  last.push({sx, sy});

  vector dx = {-1, 1, 0, 0}, dy = {0, 0, 1, -1};
  int num = 0;
  while (dis[fx][fy] == 1e8) {
    queue<vector<int>> current;
    while (last.size()) {
      auto v = last.front();
      current.push(v);
      last.pop();

      int x = v[0], y = v[1];
      diss[x][y] = 0;
      for (int i = 0; i < 4; i ++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx <= 0 || ny <= 0 || nx > r || ny > c) continue;
        if (dis[nx][ny] > dis[x][y] && a[nx][ny] == '.') {
          dis[nx][ny] = dis[x][y];
          last.push({nx, ny});
        }
      }
    }

    while (current.size()) {
      auto v = current.front();
      current.pop();

      int x = v[0], y = v[1];
      if (dis[x][y] == num + 1) last.push(v);
      if (diss[x][y] == n + n - 1) continue;

      for (int i = 0; i < 4; i ++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx <= 0 || ny <= 0 || nx > r || ny > c) continue;
        if (diss[nx][ny] > diss[x][y] + 1) {
          diss[nx][ny] = diss[x][y] + 1;
          dis[nx][ny] = num + 1;
          current.push({nx, ny});
        }
      }
    }

    num ++;
  }

  cout << dis[fx][fy] << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int T = 1;
  for (int I = 1; I <= T; I++) {
    solve();
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...