제출 #1196255

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196255		Johan	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	50 / 100	2095 ms	3072 KiB

adventure

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
  
const int MAX = 5e2 + 6;
const int LOG = 26;
const int inf = 1e18;
const int mod = 1e9 + 7;
const int block = 320;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m;
char a[MAX][MAX];
map < char , int > idx;
vector < string > pos{"N", "E", "S", "W"};
queue < pair < int , int > > q;
vector < vector < int > > d(MAX, vector < int > (MAX, inf));
bool can_go(int x, int y){
	return (x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] != 'X');
}
void bfs(int x, int y){
	d[x][y] = 0;
	q.push({x, y});
	while(q.size()){
		int xx = q.front().first;
		int yy = q.front().second;
		int ii = idx[a[xx][yy]];
		q.pop();
		for(int i = 0; i < 4; i++){
			int fx = xx, fy = yy;
			if(pos[ii] == "N")	fx--;
			if(pos[ii] == "E")	fy++;
			if(pos[ii] == "S")	fx++;
			if(pos[ii] == "W")	fy--;
			int dif = (ii < idx[a[xx][yy]] ? ii + 4 - idx[a[xx][yy]] : ii - idx[a[xx][yy]]);
			if(can_go(fx, fy) || fx == n && fy == m){
				if(d[fx][fy] > d[xx][yy] + dif){
					d[fx][fy] = d[xx][yy] + dif;
					q.push({fx, fy});
				}
			}
			ii = (ii + 1) % 4;
		}
	}
}
void _(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	idx['N'] = 0, idx['E'] = 1, idx['S'] = 2, idx['W'] = 3;
	if(a[1][1] != 'X')	bfs(1, 1);
	cout << (d[n][m] == inf ? -1 : d[n][m]) << endl;
}
 
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t = 1;
//	cin >> t;
	while(t--)  _();
}

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