제출 #313744

#제출 시각아이디문제언어결과실행 시간메모리
313744sofapudenNautilus (BOI19_nautilus)C++14
100 / 100
197 ms764 KiB
#include <bits/stdc++.h>

using namespace std;

const int maxn = 505;

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

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