Submission #290168

#	Time	Username	Problem	Language	Result	Execution time	Memory
290168		keta_tsimakuridze	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	113 ms	8036 KiB

adventure

#include<bits/stdc++.h>
#define pii pair<int,pair<int,int> > 
#define fi first
#define s second
using namespace std;
int n,m,k,i,d[1005][1005],f,D,F[1005][1005];
char a[1005][1005];
priority_queue< pii , vector<pii>,greater<pii> >q;
int main(){
	cin>>n>>m;
	for(k=1;k<=n;k++){
		for(i=1;i<=m;i++){
			cin>>a[k][i]; d[k][i]=500*500*4;
		}
	} 
	d[1][1]=0;
	q.push({0,{1,1}});
	while(q.size()){
		int x=q.top().s.fi;
		int y=q.top().s.s;
		int D=q.top().fi;
		q.pop();
		if(D>d[x][y]) continue;
		F[x][y]=1;
		if(a[x][y]=='X') continue;
		if(y<m){
			
			if(a[x][y]=='E') f=0;
			else if(a[x][y]=='N') f=1;
			else if(a[x][y]=='W') f=2;
			else f=3;
			if(d[x][y+1]>D+f){
				d[x][y+1]=D+f;
				q.push({d[x][y+1],{x,y+1}});
			}
		}
		if(y>1){
				if(a[x][y]=='W') f=0;
				else if(a[x][y]=='S') f=1;
				else if(a[x][y]=='E') f=2;
				else f=3;
			if(d[x][y-1]>D+f){
				d[x][y-1]=D+f;
				q.push({d[x][y-1],{x,y-1}});
			}
		}
		if(x<n){ 
				if(a[x][y]=='S') f=0;
				else if(a[x][y]=='E') f=1;
				else if(a[x][y]=='N') f=2;
				else if(a[x][y]=='W') f=3;
			if(d[x+1][y]>D+f){
				d[x+1][y]=D+f;
				q.push({d[x+1][y],{x+1,y}});
			}
		}//cout<<a[2][2]<<" "<<x<<" "<<y<<endl;
		if(x>1){
			
				if(a[x][y]=='N') f=0;
				else if(a[x][y]=='W') f=1;
				else if(a[x][y]=='S') f=2;
				else if(a[x][y]=='E') f=3;
			
			if(d[x-1][y]>D+f){
				d[x-1][y]=D+f;
				q.push({d[x-1][y],{x-1,y}});
			}
		}
	}
	if(!F[n][m])cout<<-1;
	else cout<<d[n][m];
}

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