#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define F first
#define S second
const int N = 500 + 10;
const int inf = 2e9;
const int mod = 998244353;
using namespace std;
int dist[N * N],n,m;
vector<pair<int,int>>g[N * N];
char a[N][N];
bool was[N * N];
map<pair<char,char>,int>cost;
int f(int i,int j) {
return (i - 1) * m + j;
}
char get(int x) {
int i = x / m + 1;
int j = x % m;
return a[i][j];
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
for(int i = 1; i < N * N; i++) dist[i] = inf;
cost[{'N','N'}] = 0;
cost[{'N','E'}] = 1;
cost[{'N','S'}] = 2;
cost[{'N','W'}] = 3;
cost[{'E','E'}] = 0;
cost[{'E','S'}] = 1;
cost[{'E','W'}] = 2;
cost[{'E','N'}] = 3;
cost[{'S','S'}] = 0;
cost[{'S','W'}] = 1;
cost[{'S','N'}] = 2;
cost[{'S','E'}] = 3;
cost[{'W','W'}] = 0;
cost[{'W','N'}] = 1;
cost[{'W','E'}] = 2;
cost[{'W','S'}] = 3;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> a[i][j];
if(a[i][j] == 'X') continue;
if(i >= 2) g[f(i,j)].pb({f(i - 1,j),cost[{a[i][j],'N'}]});
if(j >= 2) g[f(i,j)].pb({f(i,j - 1),cost[{a[i][j],'W'}]});
if(i + 1 <= n) g[f(i,j)].pb({f(i + 1,j),cost[{a[i][j],'S'}]});
if(j + 1 <= m) g[f(i,j)].pb({f(i,j + 1),cost[{a[i][j],'E'}]});
}
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
dist[f(1,1)] = 0;
pq.push({0,f(1,1)});
while(!pq.empty()) {
int dst = pq.top().F;
int u = pq.top().S;
pq.pop();
if(was[u] || get(u) == 'X') continue;
was[u] = true;
for(auto X : g[u]) {
if(dist[X.F] > dist[u] + X.S) {
dist[X.F] = dist[u] + X.S;
pq.push({dist[X.F],X.F});
}
}
}
cout << dist[f(n,m)];
return 0;
}
Compilation message
adventure.cpp: In function 'int main()':
adventure.cpp:72:7: warning: unused variable 'dst' [-Wunused-variable]
72 | int dst = pq.top().F;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
