제출 #978919

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
978919		asdfgrace	Maze (JOI23_ho_t3)	C++17	27 / 100	94 ms	15408 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));
    priority_queue<array<int, 3>> q;
    q.push({0, i0, j0});
    vis[i0][j0] = true;
    while (q.size()) {
      int ed = -q.top()[0], i = q.top()[1], j = q.top()[2];
      q.pop();
      if (ed != dist[i][j]) continue;
      for (int ni = max(i - k, 0); ni <= min(i + k, n - 1); ni++) {
        for (int nj = max(j - k, 0); nj <= min(j + k, m - 1); nj++) {
          if (ni == i && nj == j) continue;
          if (abs(i - ni) + abs(j - nj) == 1 && a[ni][nj] == '.') {
            if (dist[i][j] < dist[ni][nj]) {
              dist[ni][nj] = dist[i][j];
              q.push({-dist[ni][nj], ni, nj});
            }
          } else {
            if (dist[i][j] + 1 < dist[ni][nj]) {
              dist[ni][nj] = dist[i][j] + 1;
              q.push({-dist[ni][nj], ni, nj});
            }
          }
        }
      }
    }
    cout << dist[i1][j1] << '\n';
  }
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 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