Submission #1105276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105276		duckindog	Maze (JOI23_ho_t3)	C++17	0 / 100	1 ms	336 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 + 10, vector<char>(c + 10));
  for (int i = 1; i <= r; ++i) { 
    for (int j = 1; j <= c; ++j) cin >> a[i][j];
  }

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

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

  for (int i = 1; i <= r; ++i) { 
    for (int j = 1; j <= c; ++j) { 
      if (a[i][j] != '#') continue;
      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]);
        if (a[i + dx[t]][j + dy[t]] == '.') ad[u].push_back({v, 0});
      }
    }
  }

  int it = idx(r, c);
  for (int i = 1; i <= r; ++i) { 
    for (int j = 1; j <= c; ++j) { 
      vector<int> foo = {-1, 0, n - 1, n};   
      it += 1;

      for (int t = j; t <= min(c, j + n - 1); ++t) { 
        for (int type = 0; type < 4; ++type) { 
          if (!in(i + foo[type], t)) continue;
          int v = idx(i + foo[type], t);
          // if (i == 3 && j == 2) cerr << i + foo[type] << " " << t << "\n"; 
          ad[it].push_back({v, 1});
          ad[v].push_back({it, 1});
        }
      }

      for (int t = i; t <= min(r, i + n - 1); ++t) { 
        for (int type = 0; type < 4; ++type) { 
          if (!in(t, j + foo[type])) continue;
          int v = idx(t, j + foo[type]);
          // if (i == 3 && j == 2) cerr << t << " " << j + foo[type] << "\n";
          ad[it].push_back({v, 1});
          ad[v].push_back({it, 1});
        }
      }

      if (i <= Gr && j <= Gc && Gr <= i + n - 1 && Gc <= j + n - 1) {
        ad[it].push_back({idx(Gr, Gc), 1});
        ad[idx(Gr, Gc)].push_back({it, 1});
      }
    }
  }
  
  using pii = pair<int, int>;
  priority_queue<pii, vector<pii>, greater<>> q;
  vector<int> f(it, 1'000'000'000);
  q.push({f[idx(Sr, Sc)] = 0, idx(Sr, Sc)});
  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(Gr, Gc)] + 1) / 2 << "\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