Submission #1090268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090268		Muhammet	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	65 ms	6092 KiB

adventure

#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second

int n, m, vis[505][505];

char v[] = {'N', 'E', 'S', 'W'};

vector <vector <char>> a;

vector <vector <int>> dp;

int f(char x, char y){
	int ind = 0;
	for(int i = 0; i < 4; i++){
		if(v[i] == x){
			ind = i;
			break;
		}
	}
	int cnt = 0;
	while(1){
		if(v[ind] == y) break;
		ind++;
		if(ind == 4) ind = 0;
		cnt++;
	}
	return cnt;
}

int main(){
	cin >> n >> m;
	a.assign(n+1, vector <char> (m+1));
	dp.assign(n+1, vector <int> (m+1,1e8));
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
			if(a[i][j] == 'X') vis[i][j] = 1;
		}
	}
	priority_queue <pair<int,pair<int,int>>> q;
	q.push({0,{n,m}});
	for(int i = 0; i <= n+1; i++){
		vis[i][0] = vis[i][m+1] = 1;
	}
	for(int i = 0; i <= m+1; i++){
		vis[0][i] = vis[n+1][i] = 1;
	}
	dp[n][m] = 0;
	a[n][m] = 'E';
	while(!q.empty()){
		int i = q.top().ss.ff, j = q.top().ss.ss, w = q.top().ff;
		w *= (-1);
		q.pop();
		if((a[i][j] == 'X') or (dp[i][j] != w)) continue;
		if(vis[i][j+1] == 0 and f(a[i][j+1],'W')+dp[i][j] < dp[i][j+1]){
			dp[i][j+1] = f(a[i][j+1],'W')+dp[i][j];
			q.push({-dp[i][j+1],{i,j+1}});
		}
		if(vis[i][j-1] == 0 and f(a[i][j-1],'E')+dp[i][j] < dp[i][j-1]){
			dp[i][j-1] = f(a[i][j-1],'E')+dp[i][j];
			q.push({-dp[i][j-1],{i,j-1}});
		}
		if(vis[i+1][j] == 0 and f(a[i+1][j],'N')+dp[i][j] < dp[i+1][j]){
			dp[i+1][j] = f(a[i+1][j],'N')+dp[i][j];
			q.push({-dp[i+1][j],{i+1,j}});
		}
		if(vis[i-1][j] == 0 and f(a[i-1][j],'S')+dp[i][j] < dp[i-1][j]){
			dp[i-1][j] = f(a[i-1][j],'S')+dp[i][j];
			q.push({-dp[i-1][j],{i-1,j}});
		}
	}
	cout << (dp[1][1] == 1e8 ? -1 : dp[1][1]);
}

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