Submission #586856

#	Time	Username	Problem	Language	Result	Execution time	Memory
586856		algorithm16	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	240 ms	17232 KiB

adventure

#include <bits/stdc++.h>

#define F first
#define S second

using namespace std;

const int inf = 1e9 + 7;

typedef pair <int, int> pii;

int n, m;
int dis[507][507];
char mat[507][507];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
set <pair <int, pii> > s;
map <char, int> sm;

bool isV(int x, int y) {
	return (x >= 0 && x < n && y >= 0 && y < m);
}

int main () {
	cin >> n >> m;
	
	sm['E'] = 0;
	sm['S'] = 1;
	sm['W'] = 2;
	sm['N'] = 3;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			dis[i][j] = inf;
			s.insert({(i+j) ? inf : 0, {i, j}});
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> mat[i][j];
		}
	}
	
	dis[0][0] = 0;
	
	while (!s.empty()) {
		pair <int, pii> p = *s.begin();
		int px = p.S.F, py = p.S.S;
		for (int i = 0; i < 4; i++) {
			int cost = (4 + i - sm[mat[px][py]]) % 4;
			if (mat[px][py] == 'X') cost = inf;
			int nx = px + dx[i], ny = py + dy[i];
			if (!isV(nx, ny)) continue;
			if (dis[nx][ny] > dis[px][py] + cost) {
				s.erase({dis[nx][ny], {nx, ny}});
				dis[nx][ny] = dis[px][py] + cost;
				s.insert({dis[nx][ny], {nx, ny}});
			}
		}
		s.erase(p);
	}
	
	if (dis[n-1][m-1] == inf) {
		cout << -1; return 0;
	}
	
	cout << dis[n-1][m-1];
	
	return 0;
}

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