Submission #1307952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307952		lvs	Nautilus (BOI19_nautilus)	C++20	29 / 100	1095 ms	576 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, res, e[N];
vector <int> st;
string s;
char c[510][510];
bool used[500][510][510];
multiset <int> sm, ms;
map <char, pair<int, int>> mp;
void f(int nm, int i, int j) {
	if(used[nm][i][j]) return;
	if (nm == k) {
		used[nm][i][j] = 1;
		return;
	}
	if (s[nm] == '?' || s[nm] == 'W') {
		if (j-1 != 0 && c[i][j-1] == '.') f(nm+1, i,  j-1);
	}
	if (s[nm] == '?' || s[nm] == 'E') {
		if (j < m && c[i][j+1] == '.') f(nm+1, i, j+1);
	}
	if (s[nm] == '?' || s[nm] == 'N') {
		if (i-1 != 0 && c[i-1][j] == '.') f(nm+1, i-1, j);
	}
	if (s[nm] == '?' || s[nm] == 'S') {
		if (i < n && c[i+1][j] == '.') f(nm+1, i+1, j);
	}
	return;
}
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] == '.') f(0, i, j);
		}
	} 
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (used[k][i][j]) res++;
		}
	}cout << res;
}

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