#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vc = vector<char>;
using vvc = vector<vc>;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
const vi dx = {-1,0,1,0};
const vi dy = {0,1,0,-1};
const int inf = 1e9;
void setIO()
{
fast;
// #ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// #endif
}
int main()
{
setIO();
int n,m;//n rows, m columns
cin>>n>>m;
vvi g(n,vi(m));
vvi dist(n,vi(m,inf));
for (int i = 0;i<n;i++){
for (int j = 0;j<m;j++){
char x;
cin>>x;
if (x == 'N')g[i][j] = 0;
if (x == 'E')g[i][j] = 1;
if (x == 'S')g[i][j] = 2;
if (x == 'W')g[i][j] = 3;
if (x == 'X')g[i][j] = -1;
}
}
priority_queue<vi>q;
q.push({0,0,0});//{dist,i,j}
dist[0][0] = 0;
while (!q.empty()){
int i = q.top()[1],j = q.top()[2];
q.pop();
if (g[i][j] == -1)continue;
int x = g[i][j];
int y = (x + 1)%4;
int ni = i + dx[x];
int nj = j + dy[x];
if (ni >= 0 && ni <= n - 1 && nj >= 0 && nj <= m - 1){
if (dist[ni][nj] > dist[i][j]){
dist[ni][nj] = dist[i][j];
q.push({-dist[ni][nj],ni,nj});
}
}
int num = 1;
while (y != x){
ni = i + dx[y];
nj = j + dy[y];
//cout<<i<<" "<<j<<" "<<ni<<" "<<nj<<" "<<num<<endl;
if (ni >= 0 && ni <= n - 1 && nj >= 0 && nj <= m - 1){
if (dist[ni][nj] > dist[i][j] + num){
dist[ni][nj] = dist[i][j] + num;
q.push({-dist[ni][nj],ni,nj});
}
}
y = (y + 1)%4;
num++;
}
}
//cout<<dist[1][0]<<endl;
cout<<dist[n - 1][m - 1];
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
