이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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}, {-left[x][y], 0}, {right[x][y], 0}}) {
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |