Submission #978697

#	Time	Username	Problem	Language	Result	Execution time	Memory
978697		asdfgrace	Maze (JOI23_ho_t3)	C++17	8 / 100	91 ms	15184 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << "  "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));

/*
*/

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

const int inf = 2e9 + 5;

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  int i0, j0, i1, j1;
  cin >> i0 >> j0 >> i1 >> j1;
  i0--; j0--; i1--; j1--;
  vector<string> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  function<bool(int, int)> ok = [&] (int i, int j) {
    return i >= 0 && i < n && j >= 0 && j < m;
  };
  if (k == 1) {
    vector<vector<int>> dist(n, vector<int>(m, inf));
    deque<array<int, 3>> q;
    q.push_back({i0, j0, 0});
    dist[i0][j0] = 0;
    while (q.size()) {
      int i = q[0][0], j = q[0][1], _d = q[0][2];
      q.pop_front();
      if (dist[i][j] != _d) continue;
      for (int d = 0; d < 4; d++) {
        int ni = i + dx[d], nj = j + dy[d];
        if (!ok(ni, nj)) continue;
        if (a[ni][nj] == '.') {
          if (dist[i][j] < dist[ni][nj]) {
            dist[ni][nj] = dist[i][j];
            q.push_front({ni, nj, dist[i][j]});
          }
        } else {
          if (dist[i][j] + 1 < dist[ni][nj]) {
            dist[ni][nj] = dist[i][j] + 1;
            q.push_back({ni, nj, dist[i][j] + 1});
          }
        }
      }
    }
    cout << dist[i1][j1] << '\n';
  } else if (n * m <= 1000) {
    vector<vector<int>> dist(n, vector<int>(m, inf));
    dist[i0][j0] = 0;
    vector<vector<bool>> vis(n, vector<bool>(m, false));
    queue<array<int, 2>> q;
    q.push({i0, j0});
    vis[i0][j0] = true;
    while (q.size()) {
      int i = q.front()[0], j = q.front()[1];
      q.pop();
      for (int d = 0; d < 4; d++) {
        int ni = i + dx[d], nj = j + dy[d];
        if (!ok(ni, nj)) continue;
        if (a[ni][nj] == '.' && dist[ni][nj] > 0) {
          dist[ni][nj] = 0;
          vis[i][j] = true;
          q.push({ni, nj});
        }
      }
    }
    for (int it = 0; it < n * m; it++) {
      int best = inf, bi = -1, bj = -1;
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          if (dist[i][j] < best) {
            best = dist[i][j];
            bi = i;
            bj = j;
          }
        }
      }
      vis[bi][bj] = true;
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          dist[i][j] = min(dist[i][j], dist[bi][bj] + max((abs(i - bi) + k - 2) / k,
            (abs(j - bj) + k - 2) / k));
        }
      }
    }
    vis = vector<vector<bool>>(n, vector<bool>(m, false));
    q.push({i1, j1});
    vis[i1][j1] = true;
    while (q.size()) {
      int i = q.front()[0], j = q.front()[1];
      q.pop();
      for (int d = 0; d < 4; d++) {
        int ni = i + dx[d], nj = j + dy[d];
        if (!ok(ni, nj)) continue;
        if (a[ni][nj] == '.') {
          dist[i1][j1] = min(dist[i1][j1], dist[ni][nj]);
          vis[i][j] = true;
          q.push({ni, nj});
        }
      }
    }
    cout << dist[i1][j1] << '\n';
  }
}

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