Submission #313741

#	Time	Username	Problem	Language	Result	Execution time	Memory
313741		sofapuden	Nautilus (BOI19_nautilus)	C++14	66 / 100	1098 ms	3328 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

const int maxn = 505;

int G[maxn][maxn], dp[maxn][maxn][2], n, m, Q;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> Q;
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			char c; cin >> c;
			G[i][j] = (c == '.');
			dp[i][j][0] = G[i][j];
		}
	}
	string s; cin >> s;
	for(int i = 0; i < Q; ++i){
		for(int j = 0; j < n; ++j){
			for(int k = 0; k < m; ++k){
				int cur = 0;
				if(s[i] == '?'){
					if(j)cur |= dp[j-1][k][i&1];
					if(j!=n-1)cur |= dp[j+1][k][i&1];
					if(k)cur |= dp[j][k-1][i&1];
					if(k!=m-1)cur |= dp[j][k+1][i&1];
				}
				if(s[i] == 'N' && j != n-1)cur|=dp[j+1][k][i&1];
				if(s[i] == 'E' && k)cur|=dp[j][k-1][i&1];
				if(s[i] == 'S' && j)cur|=dp[j-1][k][i&1];
				if(s[i] == 'W' && k != m-1)cur|=dp[j][k+1][i&1];
				dp[j][k][(i+1)&1] = cur&G[j][k];
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			ans+=dp[i][j][Q&1];
		}
	}
	cout << ans << "\n";
}
			
					
	

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