이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int N = 505;
#define pii pair<int,int>
#define pb push_back
struct Edge{
int x, y, w;
};
int n, m, dist[N][N];
char c;
vector<Edge> g[N][N];
bool vis[N][N];
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n >> m;
int arr[4][2]={{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
for(int i = 0; i <= n+2; i++) for(int j = 0; j <= m+2; j++) {dist[i][j] = 1e9; vis[i][j] = 0;}
Edge e;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> c;
int co;
if(c == 'N'){
co = 0;
for(int k = 0; k < 4; k++){
e.x = i + arr[(k+co)%4][0];
e.y = j + arr[(k+co)%4][1];
e.w = k;
g[i][j].pb(e);
}
}else if(c == 'E'){
co=1;
for(int k = 0; k < 4; k++){
e.x = i + arr[(k+co)%4][0];
e.y = j + arr[(k+co)%4][1];
e.w = k;
g[i][j].pb(e);
}
}else if(c == 'S'){
co=2;
for(int k = 0; k < 4; k++){
e.x = i + arr[(k+co)%4][0];
e.y = j + arr[(k+co)%4][1];
e.w = k;
g[i][j].pb(e);
}
}else if(c == 'W'){
co=3;
for(int k = 0; k < 4; k++){
e.x = i + arr[(k+co)%4][0];
e.y = j + arr[(k+co)%4][1];
e.w = k;
g[i][j].pb(e);
}
}
}
}
dist[1][1] = 0;
priority_queue<pair<int, pii>> q;
q.push({0, {1, 1}});
while(!q.empty()){
int x = q.top().second.first, y = q.top().second.second;
q.pop();
if(vis[x][y]) continue;
vis[x][y] = 1;
for(Edge u: g[x][y]){
if(!vis[u.x][u.y] && dist[x][y] + u.w < dist[u.x][u.y]){
dist[u.x][u.y] = dist[x][y] + u.w;
q.push({-u.w, {u.x, u.y}});
}
}
}
cout << (!vis[n][m] ? -1 : dist[n][m]);
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... |