Submission #257068

#	Time	Username	Problem	Language	Result	Execution time	Memory
257068		lani1akea	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	50 / 100	2084 ms	3084 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;

int e(char a, char b) {
	if (mp[a] > mp[b]) {
		return (4 - mp[a]) + mp[b];
	} else return mp[b] - mp[a];
}

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;
	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: 0 / 50