Submission #976085

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

adventure

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int,pair<int,int>>
using namespace std;

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 vis[505][505];


signed main (){
	wheel = {'N','E','S','W'};
	int n,m; cin >> n >> m;
	for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			cin >> arr[i][j];
		}
	}
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	pq.push({0,{0,0}});
	while(!pq.empty()){
		int d = pq.top().fi;
		int x = pq.top().se.fi;
		int y = pq.top().se.se;
		pq.pop();
		if(vis[x][y]) continue;
		vis[x][y] = true;
//		cout << d << " " << x << " " << y << endl;

		if(x == m-1 && y == n-1){
			cout << d << endl;
			return 0;
		}
		if(arr[x][y] == 'X') continue;

		for(auto &a:wheel){
			int add = (mp[a] - mp[arr[x][y]] + 4)%4;
//			cout << a << " " << add << endl;
			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;
	}
	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