Submission #1201196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201196		kelenjo	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	38 / 100	1 ms	2376 KiB

adventure

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <utility>
#include <iomanip>

using namespace std;

//int main() {
//	int n, m, minAu=0, minAg=0, cv=0;
//	cin >> n >> m;
//	long long g, s;
//	cin >> g >> s;
//	vector<pair<int, int>> gr[21][21];
//	bool u[201] = { false };
//	vector<pair<pair<int, int>, pair<int, int>>> val;
//	for (int i = 0; i < m; i++) {
//		int x, y, au, ag;
//		cin >> x >> y >> au >> ag;
//		gr[x][y].push_back(make_pair(au, ag));
//		gr[y][x].push_back(make_pair(au, ag));
//		val.push_back(make_pair(make_pair(au, ag), make_pair(x, y)));
//	}
//	sort(val.begin(), val.end());
//	for (int i = 0; i < m; i++) {
//		int x = val[i].second.first, y = val[i].second.second;
//		int au = val[i].first.first, ag = val[i].first.second;
//		if (u[x]==false && u[y]==false) {
//
//		}
//		
//	}
//	for (int i = 1; i <= 3; i++) {
//		for (int j = 1; j <= 3; j++) {
//			if (gr[i][j].size() != 0 && i!=j) {
//				sort(gr[i][j].begin(), gr[i][j].end());
//				minAu = max(minAu, gr[i][j][0].first);
//			}
//		}
//	} 
//}

#define mk make_pair

int main() {
	int n, m;
	cin >> n >> m;
	char x[500][500];
	int dp[500][500] = { 0 }, u[500][500] = { 0 };
	int row[4] = { 0, 1, 0, -1 }, col[4] = {1, 0, -1, 0};
	map<char, int> mp;
	mp['E'] = 0;
	mp['S'] = 1;
	mp['W'] = 2;
	mp['N'] = 3;
	priority_queue<pair<int, pair<int, int>>> pq;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> x[i][j];
	dp[0][0] = 0;
	pq.push(mk(0, mk(0, 0)));
	while (!pq.empty()) {
		int d = -(pq.top().first);
		int r = pq.top().second.first;
		int c = pq.top().second.second;
		char ind = x[r][c];
		pq.pop();
		if (u[r][c] == 0) {
			//cout << d << ' ' << r << ' ' << c << ' ' << ind << endl;
			u[r][c] = 1;
			dp[r][c] = d;
			if (r == n - 1 && c == m - 1) break;
			for (int i = 0; i < 4; i++) {
				int nr = r + row[i], nc= c + col[i];
				if (nr >= 0 && nr < n && nc >= 0 && nc < m && u[nr][nc] == 0) {
					if (((nr != (n - 1)) || (nc != (m - 1))) && x[nr][nc] == 'X')
						continue;
					int dif = mp[ind];
					if (i >= dif) dif = i - dif;
					else dif = (3 - dif) + i+1;
					pq.push(mk(( - (d + dif)), mk(nr, nc)));
				}
			}
		}
	}
	if (u[n - 1][m - 1] == 0)
		cout << -1;
	else
		cout << dp[n - 1][m - 1];

	
}

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