#include <bits/stdc++.h>
using namespace std;
#define MAXM 510
#define MAXN 1510
long long n;
long long m;
char matrica[MAXM][10];
vector<pair<long long,long long>> adj[MAXM];
long long dist[MAXN];
void dikstra(long long poc)
{
for (long long i=0;i<MAXN;i++) dist[i]=LLONG_MAX;
dist[poc]=0;
priority_queue<pair<long long,long long>,vector<pair<long long,long long>>,greater<pair<long long,long long>>> pq;
pq.push({0,poc});
while (pq.empty()==false)
{
long long node0=pq.top().second;
long long dist0=pq.top().first;
pq.pop();
if (dist0!=dist[node0]) continue;
long long s=adj[node0].size();
for (long long i=0;i<s;i++)
{
long long node=adj[node0][i].first;
long long distt=adj[node0][i].second;
if (dist0+distt<dist[node])
{
dist[node]=distt+dist0;
pq.push({dist[node],node});
}
}
}
}
int main()
{
cin>>n>>m;
for (long long i=1;i<=n;i++)
{
for (long long j=1;j<=m;j++) cin>>matrica[i][j];
}
for (long long i=1;i<=n;i++)
{
for (long long j=1;j<=m;j++)
{
if (i==1)
{
if (j==1)
{
if (matrica[i][j]=='E')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,0});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,1});
}
if (matrica[i][j]=='S')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,3});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,0});
}
if (matrica[i][j]=='W')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,2});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,3});
}
if (matrica[i][j]=='N')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,1});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,2});
}
}
else if (j==m)
{
if (matrica[i][j]=='E')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,2});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,1});
}
if (matrica[i][j]=='S')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,1});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,0});
}
if (matrica[i][j]=='W')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,0});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,3});
}
if (matrica[i][j]=='N')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,3});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,2});
}
}
else
{
if (matrica[i][j]=='E')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,0});
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,2});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,1});
}
if (matrica[i][j]=='S')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,3});
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,1});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,0});
}
if (matrica[i][j]=='W')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,2});
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,0});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,3});
}
if (matrica[i][j]=='N')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,1});
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,3});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,2});
}
}
}
else if (i==n)
{
if (j==1)
{
if (matrica[i][j]=='E')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,0});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,3});
}
if (matrica[i][j]=='S')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,3});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,2});
}
if (matrica[i][j]=='W')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,2});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,1});
}
if (matrica[i][j]=='N')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,1});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,0});
}
}
else if (j==m)
{
if (matrica[i][j]=='E')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,2});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,3});
}
if (matrica[i][j]=='S')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,1});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,2});
}
if (matrica[i][j]=='W')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,0});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,1});
}
if (matrica[i][j]=='N')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,3});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,0});
}
}
else
{
if (matrica[i][j]=='E')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,0});
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,2});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,3});
}
if (matrica[i][j]=='S')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,3});
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,1});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,2});
}
if (matrica[i][j]=='W')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,2});
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,0});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,1});
}
if (matrica[i][j]=='N')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,1});
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,3});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,0});
}
}
}
else
{
if (j==1)
{
if (matrica[i][j]=='E')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,0});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,3});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,1});
}
if (matrica[i][j]=='S')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,3});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,2});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,0});
}
if (matrica[i][j]=='W')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,2});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,1});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,3});
}
if (matrica[i][j]=='N')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,1});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,0});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,2});
}
}
else if (j==m)
{
if (matrica[i][j]=='E')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,2});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,3});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,1});
}
if (matrica[i][j]=='S')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,1});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,2});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,0});
}
if (matrica[i][j]=='W')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,0});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,1});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,3});
}
if (matrica[i][j]=='N')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,3});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,0});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,2});
}
}
else
{
if (matrica[i][j]=='E')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,0});
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,2});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,3});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,1});
}
if (matrica[i][j]=='S')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,3});
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,1});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,2});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,0});
}
if (matrica[i][j]=='W')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,2});
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,0});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,1});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,3});
}
if (matrica[i][j]=='N')
{
adj[(i-1)*m+j].push_back({(i-1)*m+j+1,1});
adj[(i-1)*m+j].push_back({(i-1)*m+j-1,3});
adj[(i-1)*m+j].push_back({(i-1-1)*m+j,0});
adj[(i-1)*m+j].push_back({(i-1+1)*m+j,2});
}
}
}
}
}
dikstra(1);
if (dist[n*m]==LLONG_MAX) cout<<-1<<endl;
else cout<<dist[n*m]<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
444 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
444 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
444 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
