#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll INF = 1e18+7;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(long long i = a;i < b;i++)
#define rf(i,a,b) for(long long i=a;i>=b;i--)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define w(t) while(t--)
#define c(n); cin>>n;
#define p(n) cout<<n;
#define pl(n) cout<<n<<"\n";
#define ps(n); cout<<n<<" ";
#define F first
#define S second
#define pb(a) push_back(a)
#define all(x) (x).begin(), (x).end()
#define ull unsigned long long
#define vll vector<ll>
#define vii vector<ii>
#define mkp make_pair
#define ld long double
#define arrin(a,n) f(i,0,n){cin>>a[i];}
#define arrout(a,n) f(i,0,n){cout<<a[i]<<" ";}
#define prllclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define PI (2LL*acos(0))
vll visit,taken;
ll dist[500 * 500 + 5];
vector<vll> adj;
vii adj2LL[500 * 500 + 5];
priority_queue<ii,vector<ii>, greater<ii> > pq;
void dijkstra(ll s){pq.push(ii(0,s));dist[s] = 0;while(!pq.empty()){ii f = pq.top();pq.pop();ll w = f.F;ll u = f.S;if(w > dist[u]){continue;}for(auto v:adj2LL[u]){if(dist[u] + v.S < dist[v.F]){dist[v.F] = dist[u] + v.S;pq.push(ii(dist[v.F],v.F));}}}}
int main(void){
fastio;
ll n,m;
c(n);
c(m);
char arr[n][m];
f(i,0,n){
f(j,0,m){
c(arr[i][j]);
}
}
swap(n,m);
f(i,0,m){
f(j,0,n){
if(arr[i][j] == 'N'){
if(i-1 >= 0)
adj2LL[j*m+i].pb(ii(j*m+i-1,0));
if(j+1 <= m-1)
adj2LL[j*m+i].pb(ii((j+1)*m+i,1));
if(i+1 <= n-1)
adj2LL[j*m+i].pb(ii(j*m+i+1,2));
if(j-1 >= 0)
adj2LL[j*m+i].pb(ii((j-1) *m + i,3));
}
else if(arr[i][j] == 'E'){
if(i-1 >= 0)
adj2LL[j*m+i].pb(ii(j*m+i-1,3));
if(j+1 <= m-1)
adj2LL[j*m+i].pb(ii((j+1)*m+i,0));
if(i+1 <= n-1)
adj2LL[j*m+i].pb(ii(j*m+i+1,1));
if(j-1 >= 0)
adj2LL[j*m+i].pb(ii((j-1) *m + i,2));
}
else if(arr[i][j] == 'S'){
if(i-1 >= 0)
adj2LL[j*m+i].pb(ii(j*m+i-1,2));
if(j+1 <= m-1)
adj2LL[j*m+i].pb(ii((j+1)*m+i,3));
if(i+1 <= n-1)
adj2LL[j*m+i].pb(ii(j*m+i+1,0));
if(j-1 >= 0)
adj2LL[j*m+i].pb(ii((j-1) *m + i,1));
}
else if(arr[i][j] == 'W'){
if(i-1 >= 0)
adj2LL[j*m+i].pb(ii(j*m+i-1,1));
if(j+1 <= m-1)
adj2LL[j*m+i].pb(ii((j+1)*m+i,2));
if(i+1 <= n-1)
adj2LL[j*m+i].pb(ii(j*m+i+1,3));
if(j-1 >= 0)
adj2LL[j*m+i].pb(ii((j-1) *m + i,0));
}
}
}
f(i,0,n*m+5){
dist[i] = INF;
}
dijkstra(0);
ll i = n-1;
ll j = m-1;
if(dist[j*m + i] >= INF){
pl(-1);
return 0;
}
pl(dist[j*m + i]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6272 KB |
Output is correct |
| 2 |
Correct |
8 ms |
6272 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
6272 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6272 KB |
Output is correct |
| 2 |
Correct |
8 ms |
6272 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
6272 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6272 KB |
Output is correct |
| 2 |
Correct |
8 ms |
6144 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6144 KB |
Output is correct |
| 4 |
Correct |
7 ms |
6144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
6272 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
6272 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6272 KB |
Output is correct |
| 2 |
Correct |
8 ms |
6272 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
6272 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
