Submission #257087

#	Time	Username	Problem	Language	Result	Execution time	Memory
257087		lani1akea	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	1379 ms	3448 KiB

adventure

#include <bits/stdc++.h>

#define F first
#define S second
#define ll long long
#define pb push_back
#define endl '\n'

using namespace std;

const int MOD = 1e9 + 7;
const int N = 510;

int n, m, dis[N][N], used[N][N];
char g[N][N];
map<char, int> mp;
map<pair<char,char>, int> e;

void bfs(int x, int y) {
	used[x][y] = 1;
	dis[x][y] = 0;
	queue<pair<int, int>> q;
	q.push({x, y});
	while(!q.empty()) {
		pair<int, int> u = q.front();
		x = u.F, y = u.S;
		used[x][y] = 1;
		if ( x ) { // up
			if ( g[x-1][y] == 'S' and dis[x-1][y] > dis[x][y]) {
				dis[x-1][y] = dis[x][y];
				q.push({x-1,y});
			} else if ( g[x-1][y] != 'X' and  dis[x-1][y] > dis[x][y] + e[{g[x-1][y],'S'}] ) {
				dis[x-1][y] = dis[x][y] + e[{g[x-1][y], 'S'}];
				q.push({x-1,y});
			}
		} if ( y ) { // left
			if ( g[x][y-1] == 'E' and dis[x][y-1] > dis[x][y]) {
				dis[x][y-1] = dis[x][y];
				q.push({x,y-1});
			} else if ( g[x][y-1] != 'X' and  dis[x][y-1] > dis[x][y] + e[{g[x][y-1],'E'}]) {
				dis[x][y-1] = dis[x][y] + e[{g[x][y-1], 'E'}];
				q.push({x,y-1});
			}
		} if ( x < n - 1) { //down
			if ( g[x+1][y] == 'N' and dis[x+1][y] > dis[x][y]) {
				dis[x+1][y] = dis[x][y];
				q.push({x+1,y});
			} else if ( g[x+1][y] != 'X' and  dis[x+1][y] > dis[x][y] + e[{g[x+1][y],'N'}]) {
				dis[x+1][y] = dis[x][y] + e[{g[x+1][y], 'N'}];
				q.push({x+1,y});
			}
		} if (y < m - 1) {
			if ( g[x][y+1] == 'W' and dis[x][y+1] > dis[x][y]) {
				dis[x][y+1] = dis[x][y];
				q.push({x,y+1});
			} else if ( g[x][y+1] != 'X' and  dis[x][y+1] > dis[x][y] + e[{g[x][y+1],'W'}]) {
				dis[x][y+1] = dis[x][y] + e[{g[x][y+1], 'W'}];
				q.push({x,y+1});
			}
		}
		q.pop();
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	mp['N'] = 1;
	mp['E'] = 2;
	mp['S'] = 3;
	mp['W'] = 4;
	e[{'N', 'E'}] = 1;
	e[{'N', 'S'}] = 2;
	e[{'N', 'W'}] = 3;
	e[{'E', 'S'}] = 1;
	e[{'E', 'W'}] = 2;
	e[{'E', 'N'}] = 3;
	e[{'S', 'W'}] = 1;
	e[{'S', 'N'}] = 2;
	e[{'S', 'E'}] = 3;
	e[{'W', 'N'}] = 1;
	e[{'W', 'E'}] = 2;
	e[{'W', 'S'}] = 3;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			dis[i][j] = INT_MAX;
			cin >> g[i][j];
		}
	}
	bfs(n-1,m-1);
	if ( dis[0][0] == INT_MAX)
		cout << "-1\n";
	else
		cout << dis[0][0] << endl;
}

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