제출 #1329221

#제출 시각아이디문제언어결과실행 시간메모리
1329221lywoemMaze (JOI23_ho_t3)C++20
8 / 100
254 ms40440 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define l(a, b, i) for (ll i = a; i < b; i++)
#define rl(a, b, i) for (ll i = a; i >= b; i--)
#define vpair vector<pair<ll, ll>>
#define inf LLONG_MAX
#define ninf LLONG_MIN

ll N, H, W, Sr, Sc, Gr, Gc;

vector<vector<char>> grid;
vector<vector<bool>> visited;
vector<vector<ll>> dist;

ll dr[4] = {-1, 1, 0, 0};
ll dc[4] = {0, 0, -1, 1};

void dijkstra(ll start_r, ll start_c) {
    visited.assign(H + 1, vector<bool> (W + 1, false));
    dist.assign(H + 1, vector<ll> (W + 1, inf));
    priority_queue<pair<ll, pair<ll, ll>>, vector<pair<ll, pair<ll, ll>>>, greater<>> pq;

    dist[start_r][start_c] = 0;
    pq.push({0, {start_r, start_c}});

    while (!pq.empty()) {
        ll r = pq.top().second.first;
        ll c = pq.top().second.second;
        ll curdist = pq.top().first;
        pq.pop();

        if (!visited[r][c]) {
            visited[r][c] = true;

            l(0, 4, i) {
                ll nr = r + dr[i];
                ll nc = c + dc[i];

                if (nr < 1 || nr > H || nc < 1 || nc > W) continue;
                //if (grid[nr][nc] == '#') continue;

                ll w = 0; 
                if (grid[nr][nc] == '#') w = 1;

                if (dist[nr][nc] > curdist + w) {
                    dist[nr][nc] = curdist + w;
                    pq.push({dist[nr][nc], {nr, nc}});
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> H >> W >> N >> Sr >> Sc >> Gr >> Gc;
    grid.resize(H + 1, vector<char>(W + 1));

    l(1, H + 1, r) {
        string A; cin >> A;
        l(0, W, c) grid[r][c + 1] = A[c];
    }

// Crab 1
    dijkstra(Sr, Sc);
    cout << dist[Gr][Gc];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...