Submission #412294

#	Time	Username	Problem	Language	Result	Execution time	Memory
412294		ak2006	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	244 ms	16024 KiB

adventure

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vc = vector<char>;
using vvc = vector<vc>;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
const vi dx = {-1,0,1,0};
const vi dy = {0,1,0,-1};
const int inf = 1e9;
void setIO()
{
	fast;
	// #ifndef ONLINE_JUDGE
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	// #endif
}
int main()
{
	setIO();
	int n,m;//n rows, m columns
	cin>>n>>m;
	vvi g(n,vi(m));
	vvi dist(n,vi(m,inf));
	for (int i = 0;i<n;i++){
		for (int j = 0;j<m;j++){
			char x;
			cin>>x;
			if (x == 'N')g[i][j] = 0;
			if (x == 'E')g[i][j] = 1;
			if (x == 'S')g[i][j] = 2;
			if (x == 'W')g[i][j] = 3;
			if (x == 'X')g[i][j] = -1;
		}
	}
	priority_queue<vi>q;
	q.push({0,0,0});//{dist,i,j}
	dist[0][0] = 0;
	while (!q.empty()){
		int i = q.top()[1],j = q.top()[2];
		q.pop();
		if (g[i][j] == -1)continue;
		int x = g[i][j];
		int y = (x + 1)%4;
		int ni = i + dx[x];
		int nj = j + dy[x];
		if (ni >= 0 && ni <= n - 1 && nj >= 0 && nj <= m - 1){
			if (dist[ni][nj] > dist[i][j]){
				dist[ni][nj] = dist[i][j];
				q.push({-dist[ni][nj],ni,nj});
			}
		}
		int num = 1;
		while (y != x){
			ni = i + dx[y];
			nj = j + dy[y];
			if (ni >= 0 && ni <= n - 1 && nj >= 0 && nj <= m - 1){
				if (dist[ni][nj] > dist[i][j] + num){
					dist[ni][nj] = dist[i][j] + num;
					q.push({-dist[ni][nj],ni,nj});
				}
			}
			y = (y + 1)%4;
			num++;
		}
	}
	if (dist[n - 1][m - 1] >= inf)cout<<-1;
	else cout<<dist[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