제출 #832854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
832854		serifefedartar	Nautilus (BOI19_nautilus)	C++17	66 / 100	1070 ms	6644 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 300005

vector<vector<bool>> in_set;
vector<string> grid;
int main() {
	fast
	int R, C, M;
	cin >> R >> C >> M;

	grid = vector<string>(R);
	in_set = vector<vector<bool>>(R, vector<bool>(C, false));
	for (int i = 0; i < R; i++)
		cin >> grid[i];
	string way;
	cin >> way;

	vector<pair<int,int>> curr;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (grid[i][j] == '.')
				curr.push_back({i, j});
		}
	}

	vector<pair<int,int>> new_curr;
	for (int i = 0; i < M; i++) {
		new_curr = vector<pair<int,int>>();
		for (auto u : curr)
			in_set[u.f][u.s] = false;

		if (way[i] == 'W') {
			for (auto u : curr) {
				if (u.s && grid[u.f][u.s-1] == '.' && !in_set[u.f][u.s-1]) {
					new_curr.push_back({u.f, u.s-1});
					in_set[u.f][u.s-1] = true;
				}
			}
		} else if (way[i] == 'E') {
			for (auto u : curr) {
				if (u.s != C-1 && grid[u.f][u.s+1] == '.' && !in_set[u.f][u.s+1]) {
					new_curr.push_back({u.f, u.s+1});
					in_set[u.f][u.s+1] = true;
				}
			}
		} else if (way[i] == 'N') {
			for (auto u : curr) {
				if (u.f && grid[u.f-1][u.s] == '.' && !in_set[u.f-1][u.s]) {
					new_curr.push_back({u.f-1, u.s});
					in_set[u.f-1][u.s] = true;
				}
			}
		} else if (way[i] == 'S') {
			for (auto u : curr) {
				if (u.f != R-1 && grid[u.f+1][u.s] == '.' && !in_set[u.f+1][u.s]) {
					new_curr.push_back({u.f+1, u.s});
					in_set[u.f+1][u.s] = true;
				}
			}
		} else {
			for (auto u : curr) {
				if (u.s && grid[u.f][u.s-1] == '.' && !in_set[u.f][u.s-1]) {
					new_curr.push_back({u.f, u.s-1});
					in_set[u.f][u.s-1] = true;
				}
				if (u.s != C-1 && grid[u.f][u.s+1] == '.' && !in_set[u.f][u.s+1]) {
					new_curr.push_back({u.f, u.s+1});
					in_set[u.f][u.s+1] = true;
				}
				if (u.f && grid[u.f-1][u.s] == '.' && !in_set[u.f-1][u.s]) {
					new_curr.push_back({u.f-1, u.s});
					in_set[u.f-1][u.s] = true;
				}
				if (u.f != R-1 && grid[u.f+1][u.s] == '.' && !in_set[u.f+1][u.s]) {
					new_curr.push_back({u.f+1, u.s});
					in_set[u.f+1][u.s] = true;
				}
			}
		}
		swap(curr, new_curr);
	}

	cout << curr.size() << "\n";
}

• Subtask 1: 29 / 29
• Subtask 2: 37 / 37
• Subtask 3: 0 / 34