이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int w[4][4] = {
{0, 1, 2, 3},
{3, 0, 1, 2},
{2, 3, 0, 1},
{1, 2, 3, 0}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<string> t(n);
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++) {
cin >> t[i];
for (int j = 0; j < m; j++) {
if (t[i][j] == 'N') a[i][j] = 0;
if (t[i][j] == 'E') a[i][j] = 1;
if (t[i][j] == 'S') a[i][j] = 2;
if (t[i][j] == 'W') a[i][j] = 3;
if (t[i][j] == 'X') a[i][j] = 4;
}
}
multiset<tuple<int, int, int>> s;
s.insert({0, 0, 0});
const int inf = 1e9;
vector<vector<int>> dist(n, vector<int>(m, inf));
dist[0][0] = 0;
while (!s.empty()) {
auto it = s.begin();
auto val = *it;
s.erase(it);
int d = get<0>(val), x = get<1>(val), y = get<2>(val);
if (a[x][y] == 4) {
continue;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
int nd = d + w[a[x][y]][i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] > nd) {
if (dist[nx][ny] < inf) {
s.erase({dist[nx][ny], nx, ny});
}
dist[nx][ny] = nd;
s.insert({dist[nx][ny], nx, ny});
}
}
}
int ans = dist[n - 1][m - 1];
cout << (ans == inf ? -1 : ans) << '\n';
return 0;
}
# | 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... |