Submission #1239400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239400		ikrogipogi	Maze (JOI23_ho_t3)	C++20	0 / 100	0 ms	328 KiB

Main

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

const int INF = 1e9;
const int MAX = 2005;
int R, C, N;
int Sr, Sc, Gr, Gc;

char grid[MAX][MAX];
int dist[MAX][MAX];
bool visited[MAX][MAX];

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

bool in_bounds(int x, int y) {
    return x >= 0 && x < R && y >= 0 && y < C;
}

int main() {

    cin >> R >> C >> N;
    cin >> Sr >> Sc;
    cin >> Gr >> Gc;
    Sr--; Sc--; Gr--; Gc--;

    for (int i = 0; i < R; ++i)
        cin >> grid[i];

    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
            dist[i][j] = INF;

    deque<pair<int, int>> dq;
    dq.push_front({Sr, Sc});
    dist[Sr][Sc] = 0;

    while (!dq.empty()) {
        auto [x, y] = dq.front(); dq.pop_front();

        for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (in_bounds(nx, ny) && grid[nx][ny] == '.' && dist[nx][ny] > dist[x][y]) {
                dist[nx][ny] = dist[x][y];
                dq.push_front({nx, ny});
            }
        }

        for (int i = max(0, x - N + 1); i <= min(R - N, x); ++i) {
            for (int j = max(0, y - N + 1); j <= min(C - N, y); ++j) {
                for (int a = i; a < i + N; ++a) {
                    for (int b = j; b < j + N; ++b) {
                        if (dist[a][b] > dist[x][y] + 1) {
                            dist[a][b] = dist[x][y] + 1;
                            dq.push_back({a, b});
                        }
                    }
                }
            }
        }
    }

    cout << dist[Gr][Gc] << '\n';
    return 0;
}

• 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