#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
int n, m;
char mat[501][501];
map<pii, int> id;
vector<pii> G[30000];
bool in_range(int i, int j){
if(i >= 0 && i < n && j >= 0 && j < m)
return true;
return false;
}
void dijkstra(){
bool vis[n * m + 1];
int dist[n *m + 1];
for(int i = 0; i < n * m + 1; i++)
{
vis[i] = false;
dist[i] = 1e9;
}
priority_queue<pii> pq;
pq.push(mp(0,0));
dist[0] = 0;
vis[0] = true;
while(!pq.empty()){
pii state = pq.top();
pq.pop();
for(auto next : G[state.second]){
int next_city = next.first, len = next.second;
if(dist[next_city] > dist[state.second] + len){
dist[next_city] = dist[state.second] + len;
pq.push(mp(-dist[next_city], next_city));
}
}
}
cout<<dist[id[mp(n-1,m-1)]]<<endl;
}
int main(){
cin>>n>>m;
int cnt = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin>>mat[i][j];
id[mp(i,j)] = cnt;
cnt++;
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(mat[i][j]=='X')
continue;
else if(mat[i][j]=='N'){
if(in_range(i - 1, j)){
G[id[mp(i,j)]].pb(mp(id[mp(i - 1, j)], 0));
//cout<<id[mp(i,j)]<<" "<<id[mp(i - 1,j)]<<" "<<0<<endl;
}
if(in_range(i + 1, j)){
G[id[mp(i,j)]].pb(mp(id[mp(i + 1, j)], 2));
//cout<<id[mp(i,j)]<<" "<<id[mp(i + 1,j)]<<" "<<2<<endl;
}
if(in_range(i, j + 1))
{
G[id[mp(i,j)]].pb(mp(id[mp(i, j + 1)], 1));
//cout<<id[mp(i,j)]<<" "<<id[mp(i,j + 1)]<<" "<<1<<endl;
}
if(in_range(i, j - 1)){
G[id[mp(i,j)]].pb(mp(id[mp(i, j-1)], 3));
//cout<<id[mp(i,j)]<<" "<<id[mp(i,j-1)]<<" "<<3<<endl;
}
}
else if(mat[i][j]=='E'){
if(in_range(i - 1, j)){
G[id[mp(i,j)]].pb(mp(id[mp(i - 1, j)], 3));
//cout<<id[mp(i,j)]<<" "<<id[mp(i - 1,j)]<<" "<<3<<endl;
}
if(in_range(i + 1, j)){
G[id[mp(i,j)]].pb(mp(id[mp(i + 1, j)], 1));
//cout<<id[mp(i,j)]<<" "<<id[mp(i + 1,j)]<<" "<<1<<endl;
}
if(in_range(i, j + 1))
{
G[id[mp(i,j)]].pb(mp(id[mp(i, j + 1)], 0));
//cout<<id[mp(i,j)]<<" "<<id[mp(i,j + 1)]<<" "<<0<<endl;
}
if(in_range(i, j - 1)){
G[id[mp(i,j)]].pb(mp(id[mp(i, j-1)], 2));
//cout<<id[mp(i,j)]<<" "<<id[mp(i,j-1)]<<" "<<3<<endl;
}
}
else if(mat[i][j]=='S'){
if(in_range(i - 1, j)){
G[id[mp(i,j)]].pb(mp(id[mp(i - 1, j)], 2));
//cout<<id[mp(i,j)]<<" "<<id[mp(i - 1,j)]<<" "<<2<<endl;
}
if(in_range(i + 1, j)){
G[id[mp(i,j)]].pb(mp(id[mp(i + 1, j)], 0));
//cout<<id[mp(i,j)]<<" "<<id[mp(i + 1,j)]<<" "<<0<<endl;
}
if(in_range(i, j + 1))
{
G[id[mp(i,j)]].pb(mp(id[mp(i, j + 1)], 3));
}
if(in_range(i, j - 1)){
G[id[mp(i,j)]].pb(mp(id[mp(i, j-1)], 1));
}
}
else if(mat[i][j]=='W'){
if(in_range(i - 1, j)){
G[id[mp(i,j)]].pb(mp(id[mp(i - 1, j)], 1));
//cout<<id[mp(i,j)]<<" "<<id[mp(i - 1,j)]<<" "<<1<<endl;
}
if(in_range(i + 1, j)){
G[id[mp(i,j)]].pb(mp(id[mp(i + 1, j)], 3));
//cout<<id[mp(i,j)]<<" "<<id[mp(i + 1,j)]<<" "<<3<<endl;
}
if(in_range(i, j + 1))
{
G[id[mp(i,j)]].pb(mp(id[mp(i, j + 1)], 2));
}
if(in_range(i, j - 1)){
G[id[mp(i,j)]].pb(mp(id[mp(i, j-1)], 0));
}
}
else
{
assert(false);
}
}
}
dijkstra();
}
Compilation message
adventure.cpp: In function 'void dijkstra()':
adventure.cpp:20:7: warning: variable 'vis' set but not used [-Wunused-but-set-variable]
20 | bool vis[n * m + 1];
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
1004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
1004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1132 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1004 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
1132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
1004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
