Submission #261461

#	Time	Username	Problem	Language	Result	Execution time	Memory
261461		EJOI2019Andrew	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	135 ms	21500 KiB

adventure

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef vector<int>vi;
typedef vector<ii> vii;
vector<vii> vec;
vi dist;
priority_queue<ii,vii,greater<ii>> pq;
#define INF 1000000007
void dijkstra(int s)
{
pq.push(ii(0,s));
dist[s]=0;
while(!pq.empty())
{
ii fr=pq.top();
pq.pop();
int w=fr.first;
int u=fr.second;
if(w>dist[u])
continue;
for(int i=0; i<vec[u].size(); ++i)
{
ii v=vec[u][i];
if(dist[u]+v.second<dist[v.first])
{
dist[v.first]=dist[u]+v.second;
pq.push(ii(dist[v.first],v.first));
}
}
}
}
int cost(char a,char b)
{
int aa,bb;
if(a=='E')
aa=1;
else if(a=='S')
aa=2;
else if(a=='W')
aa=3;
else
aa=4;
if(b=='E')
bb=1;
else if(b=='S')
bb=2;
else if(b=='W')
bb=3;
else
bb=4;
if(aa<=bb)
return bb-aa;
return 4-aa+bb;
}
int main()
{
int n,m;
cin>>n>>m;
char arr[n][m];
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)
cin>>arr[i][j];
vec.assign(n*m+1,vii());
dist.assign(n*m+1,INF);
for(int i=0; i<n; ++i)
{
for(int j=0; j<m; ++j)
{
if(arr[i][j]!='X')
{
if(i-1>=0&&((arr[i-1][j]=='X'&&i-1==n-1&&j==m-1)||arr[i][j]!='X'))
vec[i*m+j].push_back(ii((i-1)*m+j,cost(arr[i][j],'N')));
if(i+1<n&&((arr[i-1][j]=='X'&&i-1==n-1&&j==m-1)||arr[i][j]!='X'))
vec[i*m+j].push_back(ii((i+1)*m+j,cost(arr[i][j],'S')));
if(j-1>=0&&((arr[i-1][j]=='X'&&i-1==n-1&&j==m-1)||arr[i][j]!='X'))
vec[i*m+j].push_back(ii(i*m+j-1,cost(arr[i][j],'W')));
if(j+1<m&&((arr[i-1][j]=='X'&&i-1==n-1&&j==m-1)||arr[i][j]!='X'))
vec[i*m+j].push_back(ii(i*m+j+1,cost(arr[i][j],'E')));
}
}
}
dijkstra(0);
if(dist[n*m-1]==INF)
cout<<-1;
else
cout<<dist[n*m-1];
}

Compilation message (stderr)

adventure.cpp: In function 'void dijkstra(int)':
adventure.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0; i<vec[u].size(); ++i)
              ~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 16 / 16
• Subtask 5: 50 / 50