제출 #1256900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256900		antonn	Maze (JOI23_ho_t3)	C++20	100 / 100	1890 ms	147272 KiB

Main

#include <bits/stdc++.h>

#define all(a) a.begin(), a.end()
using namespace std;
typedef long long ll;

int dx4[] = {1, -1, 0, 0};
int dy4[] = {0, 0, 1, -1};

int dx8[] = {1, -1, 0, 0, 1, 1, -1, -1};
int dy8[] = {0, 0, 1, -1, -1, 1, -1, 1};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int r, c, n, sr, sc, gr, gc;
    cin >> r >> c >> n >> sr >> sc >> gr >> gc;
    vector<string> a(r + 1);
    for (int i = 1; i <= r; i++) cin >> a[i], a[i] = "#" + a[i];
    
    vector<vector<pair<int, int>>> dist(r + 1, vector<pair<int, int>>(c + 1, {1e9, 1e9}));
    vector<vector<bool>> vis(r + 1, vector<bool>(c + 1));
    priority_queue<array<ll, 4>> pq;
    dist[sr][sc] = {0, n - 1};
    pq.push({0, -(n - 1), sr, sc});
    while (!pq.empty()) {
        int x = pq.top()[2];
        int y = pq.top()[3];
        pq.pop();
        if (vis[x][y]) continue;
        vis[x][y] = 1;
        for (int dir = 0; dir < 4; dir++) {
            int newx = x + dx4[dir];
            int newy = y + dy4[dir];
            if (1 <= newx && newx <= r && 1 <= newy && newy <= c) {
                if (a[newx][newy] == '.') {
                    pair<int, int> p = {dist[x][y].first, n - 1};
                    if (dist[newx][newy] > p) {
                        dist[newx][newy] = p;
                        pq.push({-p.first, -p.second, newx, newy});
                    }
                }
                pair<int, int> p = {dist[x][y].first + 1, 0};
                if (dist[newx][newy] > p) {
                    dist[newx][newy] = p;
                    pq.push({-p.first, -p.second, newx, newy});
                }
            }
        }
        if (dist[x][y].second < n - 1) {
            for (int dir = 0; dir < 8; dir++) {
                int newx = x + dx8[dir];
                int newy = y + dy8[dir];
                if (1 <= newx && newx <= r && 1 <= newy && newy <= c) {
                    pair<int, int> p = {dist[x][y].first, dist[x][y].second + 1};
                    if (dist[newx][newy] > p) {
                        dist[newx][newy] = p;
                        pq.push({-p.first, -p.second, newx, newy});
                    }
                }
            }
        }
    }
    cout << dist[gr][gc].first << "\n";
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 19 / 19
• Subtask 7: 8 / 8
• Subtask 8: 6 / 6