Submission #1105317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105317		vjudge1	Maze (JOI23_ho_t3)	C++17	27 / 100	2099 ms	87032 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];
  }
  auto in = [&](int x, int y) { return 1 <= x && x <= r && 1 <= y && y <= c; };

  vector<vector<int>> f(r + 10, vector<int>(c + 10, 1'000'000'000));


  auto getSquare = [&](int x, int y, int way, int type) { 
    vector<pair<int, int>> ret = {{x, y}};

    for (int t = 0; t < 4; ++t) { 
      for (int i = 1; i < n; ++i) { 
        x += dx[way]; y += dy[way];
        ret.push_back({x, y});
      }
      way = (way + type + 4) % 4;
    }

    return ret;
  };

  deque<pair<int, int>> q;
  q.push_back({Sr, Sc});
  f[Sr][Sc] = 0;
  while (q.size()) { 
    auto [x, y] = q.front(); q.pop_front();

    if (abs(Gr - x) <= n && abs(Gc - y) <= n) { f[Gr][Gc] = min(f[Gr][Gc], f[x][y] + 1); }

    for (int t = 0; t < 4; ++t) { 
      int nX = x + dx[t], nY = y + dy[t];
      if (!in(nX, nY) || a[nX][nY] == '#') continue;
      if (f[nX][nY] > f[x][y]) {
        f[nX][nY] = f[x][y];
        q.push_front({nX, nY});
      }
    }

    for (int t = 0; t < 4; ++t) { 
      int stX = x + dx[t], stY = y + dy[t];

      for (int type = -1; type <= 1; type += 2) { 
        for (const auto& [nX, nY] : getSquare(stX, stY, t, type)) { 
          if (!in(nX, nY)) continue; 
          if (f[nX][nY] > f[x][y] + 1) { 
            f[nX][nY] = f[x][y] + 1;
            q.push_back({nX, nY});
          }
        }
      }
    }
  }

  cout << f[Gr][Gc] << "\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