제출 #800614

#제출 시각아이디문제언어결과실행 시간메모리
800614tch1cherin포탈들 (BOI14_portals)C++17
0 / 100
1 ms256 KiB
#include <bits/stdc++.h> using namespace std; template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>; int main() { cin.tie(nullptr)->sync_with_stdio(false); int N, M; cin >> N >> M; vector<string> S(N + 2, string(M + 2, '#')); for (int i = 1; i <= N; i++) { string v; cin >> v; for (int j = 1; j <= M; j++) { S[i][j] = v[j - 1]; } } N += 2, M += 2; vector<vector<int>> up(N, vector<int>(M, -1)), down(N, vector<int>(M, -1)); vector<vector<int>> left(N, vector<int>(M, -1)), right(N, vector<int>(M, -1)); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (S[i][j] != '#') { up[i][j] = up[i - 1][j] + 1; left[i][j] = left[i][j - 1] + 1; } } } for (int i = N - 1; i >= 0; i--) { for (int j = M - 1; j >= 0; j--) { if (S[i][j] != '#') { down[i][j] = down[i + 1][j] + 1; right[i][j] = right[i][j + 1] + 1; } } } queue<pair<int, int>> q; vector<vector<int>> nearest_wall(N, vector<int>(M, INT_MAX)); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (S[i][j] == '#') { q.push({i, j}); nearest_wall[i][j] = 0; } } } while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (auto [dx, dy] : vector<pair<int, int>> {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) { int i = x + dx, j = y + dy; if (i >= 0 && j >= 0 && i < N && j < M && nearest_wall[i][j] == INT_MAX) { nearest_wall[i][j] = nearest_wall[x][y] + 1; q.push({i, j}); } } } min_heap<tuple<int, int, int>> pq; vector<vector<int>> dist(N, vector<int>(M, INT_MAX)); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (S[i][j] == 'S') { pq.push({dist[i][j] = 0, i, j}); } } } while (!pq.empty()) { auto [d, x, y] = pq.top(); pq.pop(); if (d == dist[x][y]) { for (auto [dx, dy] : vector<pair<int, int>> {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-up[x][y], 0}, {down[x][y], 0}, {0, -left[x][y]}, {0, right[x][y]}}) { int w = max(abs(dx), abs(dy)) == 1 ? 1 : nearest_wall[x][y]; int i = x + dx, j = y + dy; if (i >= 0 && i < N && j >= 0 && j < M && dist[i][j] > dist[x][y] + w) { pq.push({dist[i][j] = dist[x][y] + w, i, j}); } } } } for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (S[i][j] == 'C') { cout << dist[i][j] << "\n"; } } } }
#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...