Submission #1214845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214845		mdn2002	Maze (JOI23_ho_t3)	C++20	100 / 100	1332 ms	386540 KiB

Main

/*
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};
  vector dxx = {-1, 1, 0, 0, -1, 1, -1, 1}, dyy = {0, 0, 1, -1, -1, -1, 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) continue;

      for (int i = 0; i < 8; i ++) {
        int nx = x + dxx[i], ny = y + dyy[i];
        if (nx <= 0 || ny <= 0 || nx > r || ny > c) continue;
        if (i >= 4 && dis[x][y] == num) continue;
        if (diss[nx][ny] > diss[x][y] + 1 && dis[nx][ny] == 1e8) {
          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();
  }
}

• 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