제출 #584785

#제출 시각아이디문제언어결과실행 시간메모리
584785penguinhackerNautilus (BOI19_nautilus)C++17
100 / 100
85 ms668 KiB
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast")

#define ll long long
#define ar array
 
const int mxN=500;
int n, m, q;
bitset<mxN> mask[mxN], dp[mxN];
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> q;
	for (int i=0; i<n; ++i) {
		string s;
		cin >> s;
		for (int j=0; j<m; ++j)
			if (s[j]=='.')
				mask[i][j]=1, dp[i][j]=1;
	}
	string query;
	cin >> query;
	for (char c : query) {
		bitset<mxN> ndp[mxN];
		if (c=='W'||c=='?')
			for (int i=0; i<n; ++i)
				ndp[i]|=(dp[i]>>1)&mask[i];
		if (c=='E'||c=='?')
			for (int i=0; i<n; ++i)
				ndp[i]|=(dp[i]<<1)&mask[i];
		if (c=='N'||c=='?')
			for (int i=1; i<n; ++i)
				ndp[i-1]|=dp[i]&mask[i-1];
		if (c=='S'||c=='?')
			for (int i=0; i+1<n; ++i)
				ndp[i+1]|=dp[i]&mask[i+1];
		for (int i=0; i<n; ++i)
			swap(dp[i], ndp[i]);
	}
	int ans=0;
	for (int i=0; i<n; ++i)
		ans+=dp[i].count();
	cout << ans;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...