Submission #1086912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086912		mar	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	12 / 100	1 ms	604 KiB

adventure

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pii pair<int,pair<int,int>>
 
 char arr[505][505];
map<char,int> dirx = {
	{'N', -1},
    {'E', 0},
    {'S', 1},
    {'W', 0},
};
map<char,int> diry = {
	{'N', 0},
    {'E', 1},
    {'S', 0},
    {'W', -1},
};
map <char,int> mp = {
    {'N', 0},
    {'E', 1},
    {'S', 2},
    {'W', 3},
};
 
 vector<char> wheel(4);
 bool visited[505][505];
 int n,m;
 bool flag=0;
 
void bfs(){
    priority_queue<pii,vector<pii>,greater<pii>> pq;
	pq.push({0,{0,0}});
	while(!pq.empty()){
		int d = pq.top().f;
		int x = pq.top().s.f;
		int y = pq.top().s.s;
		pq.pop();
		if(visited[x][y]) continue;
		
		if(x == m-1 && y == n-1){
			cout << d << endl;
			flag=1;
			return;
		}
		visited[x][y] = true;
		if(arr[x][y] == 'X') continue;
		for(auto &a:wheel){
			int add = (mp[a] - mp[arr[x][y]] +4)%4;
			if(x+dirx[a]<0 || y+diry[a]<0 || y+diry[a]>=n || x+dirx[a]>=m) continue;
			pq.push({d + add,{x + dirx[a],y + diry[a]}});
		}
//		cout << endl;
	}
}
 
int main (){
	wheel = {'N','E','S','W'};
	 cin >> n >> m;
	for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			cin >> arr[i][j];
		}
	}
	bfs();
	if(!flag)cout << "-1\n";
	
	return 0;
}

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