Submission #773956

#	Time	Username	Problem	Language	Result	Execution time	Memory
773956		Dzadzo	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	72 ms	8980 KiB

adventure

#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vector<int>>
#define INF LLONG_MAX
#define MOD 1000000009
#define MAXN 100000
using namespace std;
int kx[4]={1,-1,0,0};
int ky[4]={0,0,1,-1};
main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	vector <vector < char >> d(n+1,vector <char> (m+1));
	int dist[n+1][m+1];
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			cin>>d[i][j];
			if (d[i][j]=='N')d[i][j]='u';
			if (d[i][j]=='S')d[i][j]='d';
			if (d[i][j]=='E')d[i][j]='r';
			if (d[i][j]=='W')d[i][j]='l';
			dist[i][j]=INF;
		}
	}
	priority_queue <pair <int,pii>> q;
	dist[1][1]=0;
	q.push({0,{1,1}});
	while (!q.empty()){
		pair <int,pii> p=q.top();
		q.pop();
		int x=p.S.F;
		int y=p.S.S;
		int val[4];
		if (d[x][y]=='X')continue;
		if (d[x][y]=='d'){
			val[0]=0;
			val[1]=2;
			val[2]=3;
			val[3]=1;
		}
		if (d[x][y]=='u'){
			val[0]=2;
			val[1]=0;
			val[2]=1;
			val[3]=3;
		}
		if (d[x][y]=='r'){
			val[0]=1;
			val[1]=3;
			val[2]=0;
			val[3]=2;
		}
		if (d[x][y]=='l'){
			val[0]=3;
			val[1]=1;
			val[2]=2;
			val[3]=0;
		}		
		for (int i=0;i<4;i++){
			int curx=x+kx[i];
			int cury=y+ky[i];
			if (curx==0 || cury==0 || curx==n+1 || cury==m+1)continue;
			if (dist[curx][cury]>dist[x][y]+val[i]){
				dist[curx][cury]=dist[x][y]+val[i];
				q.push({-dist[curx][cury],{curx,cury}});
			}
			
		}
	}
	if (dist[n][m]==INF)cout<<-1;else
	cout<<dist[n][m];
}

Compilation message (stderr)

adventure.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main() {
      | ^~~~

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