Submission #838001

#	Time	Username	Problem	Language	Result	Execution time	Memory
838001		gun_gan	Maze (JOI23_ho_t3)	C++17	0 / 100	86 ms	188284 KiB

Main

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

const int MX = 6e6 + 5;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int N, R, C;
int sc, sr, gc, gr;
string s[MX];

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);

      cin >> R >> C >> N;
      cin >> sr >> sc >> gr >> gc;
      for(int i = 0; i < R; i++) cin >> s[i];
      sc--, sr--, gc--, gr--;

      vector<vector<int>> dist(R, vector<int>(C, 1e9));
      vector<vector<bool>> vis(R, vector<bool>(R));

      deque<pair<int,int>> dq;
      dq.push_back({sr, sc});
      dist[sr][sc] = 0;
      while(!dq.empty()) {
            auto [x, y] = dq.front(); dq.pop_front();
            if(vis[x][y]) continue;
            vis[x][y] = 1;
            for(int r = max(0, x - N); r <= min(R - 1, x + N); r++) {
                  for(int c = max(0, y - N); c <= min(C - 1, y + N); c++) {
                        if((abs(r - x) < N || abs(c - y) < N) && dist[r][c] > dist[x][y] + 1) {
                              dist[r][c] = dist[x][y] + 1;
                              dq.push_back({r, c});
                        }
                  } 
            }

            for(int k = 0; k < 4; k++) {
                  int r = x + dx[k], c = y + dy[k];
                  if(r >= 0 && r < R && c >= 0 && c < C && dist[r][c] > dist[x][y] && s[r][c] == '.') {
                        dist[r][c] = dist[x][y];
                        dq.push_front({r, c});
                  }
            }
      }

      cout << dist[gr][gc] << '\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