Submission #1307961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307961		lvs	Nautilus (BOI19_nautilus)	C++20	66 / 100	1096 ms	5308 KiB

nautilus

#include <bits/stdc++.h>
#define int long long
#define zet ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 1e5+555, M = 5e4+557, mod = 1e9+7;
int n, m, k, it, res, e[N];
vector <int> st;
string s;
char c[510][510];
bool used[510][510];
queue <pair<int, int>> q, qq;
void f(int it) {
	while(!q.empty()) {
		int i = q.front().first;
		int j = q.front().second;
		q.pop();
		if(s[it] == '?' || s[it] == 'E') {
			if (j < m && !used[i][j+1] && c[i][j+1] == '.') {
				used[i][j+1] = 1;
				qq.push({i, j+1});
			}
		}
		if(s[it] == '?' || s[it] == 'W') {
			if (j > 1 && !used[i][j-1] && c[i][j-1] == '.') {
				used[i][j-1] = 1;
				qq.push({i, j-1});
			}
		}
		if(s[it] == '?' || s[it] == 'N') {
			if (i > 1 && !used[i-1][j] && c[i-1][j] == '.') {
				used[i-1][j] = 1;
				qq.push({i-1, j});
			}
		}
		if(s[it] == '?' || s[it] == 'S') {
			if (i < n && !used[i+1][j] && c[i+1][j] == '.') {
				used[i+1][j] = 1;
				qq.push({i+1, j});
			}
		}
	}
	return;
}
map <char, pair<int, int>> mp;
signed main() {
	zet
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) cin >> c[i][j];
	}
	cin >> s;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (c[i][j] == '.') q.push({i, j});
		}
	} 
	while (it < k) {
		f(it);
		it++;
		swap(q, qq);
		for (int i = 1; i <= n; i++) {
			for (int j = 1;j <= m; j++) used[i][j] = 0;
		}
	}
	cout << q.size();
}

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