Submission #746527

#	Time	Username	Problem	Language	Result	Execution time	Memory
746527		pera	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	106 ms	5748 KiB

adventure

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

const ll mod = 1e9 + 7;

int dx[4] = {1 , -1 , 0 , 0};
int dy[4] = {0 , 0 , 1 , -1};

int w[4] = {2 , 4 , 1 , 3};

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	map<char , int> to;
	to['E'] = 1 , to['S'] = 2 , to['W'] = 3 , to['N'] = 4;
	int n , m;cin >> n >> m;
	vector<vector<int>> a(n + 1 , vector<int>(m + 1)) , d(n + 1 , vector<int>(m + 1));
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			char c;cin >> c;
			a[i][j] = to[c];
		}
	}
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			d[i][j] = INT_MAX;
		}
	}
	d[1][1] = 0;
	priority_queue<pair<int , pair<int , int>> , vector<pair<int , pair<int , int>>> , greater<pair<int , pair<int , int>>>> pq;
	pq.push({0 , {1 , 1}});
	while(!pq.empty()){
		auto x = pq.top(); pq.pop();
		int i = x.second.first , j = x.second.second , s = x.first;
		if(s != d[i][j] || !a[i][j]) continue;
		for(int k = 0;k < 4;k ++){
			int ti = i + dx[k] , tj = j + dy[k];
			if(1 <= ti && ti <= n && 1 <= tj && tj <= m){
				int c = 0;
				if(w[k] < a[i][j]) c = 4 - a[i][j] + w[k];
				else c = w[k] - a[i][j];
			//	cout << i << " " << j << "  to : " << ti << " " << tj << " c: " << c << endl;
				if(s + c < d[ti][tj]){
					d[ti][tj] = s + c;
					pq.push({d[ti][tj] , {ti , tj}});
				}
			}
		}
	}/*
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			cout << d[i][j] << " ";
		}
		cout << endl;
	}*/
	cout << (d[n][m] == INT_MAX ? -1 : d[n][m]) << endl;
}

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