Submission #914297

#TimeUsernameProblemLanguageResultExecution timeMemory
914297NK_Nautilus (BOI19_nautilus)C++17
100 / 100
181 ms157780 KiB
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

const int nax = 505;
using B = bitset<nax>;
template<class T> using V = vector<T>;
using vi = V<int>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M, K; cin >> N >> M >> K;
	V<B> A(N); for(int i = 0; i < N; i++) {
		string S; cin >> S;
		for(int j = 0; j < M; j++) A[i][j] = (S[j] == '.');
	} 

	string O; cin >> O; 

	V<V<B>> dp(K+1, V<B>(N));
	for(int i = 0; i < N; i++) dp[0][i] = A[i];

	auto perform = [&](int i, char c) {
		if (c == 'N') for(int r = 1; r < N; r++) dp[i + 1][r - 1] |= dp[i][r] & A[r - 1];
		if (c == 'S') for(int r = 0; r < N - 1; r++) dp[i + 1][r + 1] |= dp[i][r] & A[r + 1];
		if (c == 'W') for(int r = 0; r < N; r++) dp[i + 1][r] |= (dp[i][r] >> 1) & A[r];
		if (c == 'E') for(int r = 0; r < N; r++) dp[i + 1][r] |= (dp[i][r] << 1) & A[r];
	};

	for(int i = 0; i < K; i++) {
		if (O[i] == '?') for(auto& c : "NWES") perform(i, c);
		else perform(i, O[i]);

		// cout << "OPER: " << i << " " << O[i] << endl;
		// for(int r = 0; r < N; r++) {
		// 	for(int c = 0; c < M; c++) cout << dp[i][r][c];
		// 	cout << nl;
		// }
	}

	int ans = 0;
	// for(int r = 0; r < N; r++) {
	// 	for(int c = 0; c < M; c++) cout << dp.back()[r][c];
	// 	cout << nl;
	// }

	for(int r = 0; r < N; r++) ans += dp.back()[r].count();
	cout << ans << nl;

	exit(0-0);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...