#include <bits/stdc++.h>
using namespace std;
const long long MAX=250010;
vector<pair<long long,long long> > graph[MAX];
long long n,m;
char mat[501][501];
long long dist[MAX];
bool vis[MAX];
long long get(long long i, long long j)
{
return i*m+j;
}
struct node
{
long long idx,cost;
node() {};
node(long long i, long long c)
{
idx=i;
cost=c;
}
bool operator< (const node &tmp)const
{
return cost>tmp.cost;
}
};
long long dijkstra(long long si, long long sj)
{
priority_queue<node> q;
for(long long i=0; i<n*m; i++)
{
vis[i]=false;
dist[i]=INT_MAX;
}
q.push(node{si,0});
while(!q.empty())
{
auto curr=q.top();
q.pop();
if(vis[curr.idx])continue;
vis[curr.idx]=true;
if(curr.idx==sj)return dist[curr.idx];
for(long long i=0; i<graph[curr.idx].size(); i++)
{
long long neighbour=graph[curr.idx][i].first;
long long val=graph[curr.idx][i].second;
if(dist[neighbour]>curr.cost+val)
{
dist[neighbour]=curr.cost+val;
q.push(node{neighbour,dist[neighbour]});
}
}
}
return -1;
}
int main()
{
cin>>n>>m;
for(long long i=0; i<n; i++)
{
for(long long j=0; j<m; j++)
{
cin>>mat[i][j];
}
}
for(long long i=0; i<n; i++)
{
for(long long j=0; j<m; j++)
{
if(mat[i][j]=='X')continue;
if(i+1<n)
{
long long a=get(i,j);
long long b=get(i+1,j);
if(mat[i][j]=='S')
{
graph[a].push_back({b,0});
}
else
{
if(mat[i][j]=='E')
{
graph[a].push_back({b,1});
}
else if(mat[i][j]=='N')
{
graph[a].push_back({b,2});
}
else if(mat[i][j]=='W')
{
graph[a].push_back({b,3});
}
}
}
if(j+1<m)
{
long long a=get(i,j);
long long b=get(i,j+1);
if(mat[i][j]=='E')
{
graph[a].push_back({b,0});
}
else
{
if(mat[i][j]=='N')
{
graph[a].push_back({b,1});
}
else if(mat[i][j]=='W')
{
graph[a].push_back({b,2});
}
else if(mat[i][j]=='S')
{
graph[a].push_back({b,3});
}
}
}
if(j-1>=0)
{
long long a=get(i,j);
long long b=get(i,j-1);
if(mat[i][j]=='W')
{
graph[a].push_back({b,0});
}
else
{
if(mat[i][j]=='S')
{
graph[a].push_back({b,1});
}
else if(mat[i][j]=='E')
{
graph[a].push_back({b,2});
}
else if(mat[i][j]=='N')
{
graph[a].push_back({b,3});
}
}
}
if(i-1>=0)
{
long long a=get(i,j);
long long b=get(i-1,j);
if(mat[i][j]=='N')
{
graph[a].push_back({b,0});
}
else
{
if(mat[i][j]=='W')
{
graph[a].push_back({b,1});
}
else if(mat[i][j]=='S')
{
graph[a].push_back({b,2});
}
else if(mat[i][j]=='E')
{
graph[a].push_back({b,3});
}
}
}
}
}
long long res=dijkstra(0,get(n-1,n-1));
if(res==INT_MAX)res=-1;
cout<<res<<endl;
return 0;
}
Compilation message
adventure.cpp: In function 'long long int dijkstra(long long int, long long int)':
adventure.cpp:44:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(long long i=0; i<graph[curr.idx].size(); i++)
| ~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8536 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8536 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
2 ms |
8540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8536 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
