Submission #1105272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105272		duckindog	Maze (JOI23_ho_t3)	C++17	0 / 100	1 ms	508 KiB

Main

#include <bits/stdc++.h>

using namespace std;

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

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  int r, c, n; cin >> r >> c >> n;
  int Sr, Sc; cin >> Sr >> Sc;
  int Gr, Gc; cin >> Gr >> Gc;

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

  vector<vector<pair<int, int>>> ad(2 * r * c);

  auto in = [&](int x, int y) { return 0 <= x && x < r && 0 <= y && y < r; };
  auto idx = [&](int i, int j) { return i * c + j; };

  for (int i = 0; i < r; ++i) { 
    for (int j = 0; j < c; ++j) { 
      int u = idx(i, j);
      for (int t = 0; t < 4; ++t) { 
        if (!in(i + dx[t], j + dy[t])) continue;
        int v = idx(i + dx[t], j + dy[t]);
        ad[u].push_back({v, 0});
      }
    }
  }

  int it = idx(r - 1, c - 1);
  for (int i = 0; i < r; ++i) { 
    for (int j = 0; j < c; ++j) { 
      
      for (int t = j; t < min(c, j + n); ++t) { 
        for (int type = 0; type <= 1; ++type) { 
          if (!in(!type ? i - 1 : i + n, t)) continue;
          int v = idx(!type ? i - 1 : i + n, t);
          ad[it].push_back({v, 1});
          ad[v].push_back({it, 1});
        }
      }

      for (int t = i; t < min(r, i + n); ++t) { 
        for (int type = 0; type <= 1; ++type) { 
          if (!in(t, !type ? j - 1 : j + n)) continue;
          int v = idx(t, !type ? j - 1 : j + n);
          ad[it].push_back({v, 1});
          ad[v].push_back({it, 1});
        }
      }

      if (i <= r - 1 && j <= c - 1 && r - 1 < i + n && c - 1 < j + n) {
        ad[it].push_back({idx(r - 1, c - 1), 1});
        ad[idx(r - 1, c - 1)].push_back({it, 1});
      }
    }
  }

  using pii = pair<int, int>;
  priority_queue<pii, vector<pii>, greater<>> q;
  vector<int> f(2 * r * c, 1'000'000'000);
  q.push({f[0] = 0, 0});
  while (q.size()) { 
    auto [d, u] = q.top(); q.pop();
    if (d != f[u]) continue;
    for (const auto& [v, w] : ad[u])
      if (f[v] > d + w) q.push({f[v] = d + w, v});
  }

  cout << f[idx(r - 1, c - 1)] << "\n";
}

• Subtask 1: 0 / 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