Submission #767348

#	Time	Username	Problem	Language	Result	Execution time	Memory
767348		ihceker	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	38 / 100	1 ms	320 KiB

adventure

#include<bits/stdc++.h>
#define int long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

int n,m,vis[505][505];
char arr[505][505];
map<char,int>mp;

int f(char a,char b){
	return (mp[b]-mp[a]+4)%4;
}

bool f2(int a,int b){
	if(a<0 || a>=n || b<0 || b>=m)return false;
	if(vis[a][b])return false;
	if(arr[a][b]=='X' && !(a==n-1 && b==m-1))return false;
	return true;
}

int32_t main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>arr[i][j];
		}
	}
	mp['N']=1;
	mp['E']=2;
	mp['S']=3;
	mp['W']=4;
	priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>>pq;
	pq.push({0,{0,0}});
	while(!pq.empty()){
		int x=pq.top().ff;
		int y=pq.top().ss.ff;
		int z=pq.top().ss.ss;
		pq.pop();
		if(vis[y][z]==1)continue;
		vis[y][z]=1;
		if(y==n-1 && z==m-1){
			cout<<x<<endl;
			return 0;
		}
		if(f2(y+1,z))pq.push({x+f(arr[y][z],'S'),{y+1,z}});
		if(f2(y-1,z))pq.push({x+f(arr[y][z],'N'),{y-1,z}});
		if(f2(y,z+1))pq.push({x+f(arr[y][z],'E'),{y,z+1}});
		if(f2(y,z-1))pq.push({x+f(arr[y][z],'W'),{y,z-1}});
	}
	cout<<"-1"<<endl;
}

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