제출 #477502

#제출 시각아이디문제언어결과실행 시간메모리
477502Sohsoh84Nautilus (BOI19_nautilus)C++17
100 / 100
245 ms900 KiB
// ¯\_(ツ)_/¯
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
 
#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;
 
const ll MAXN = 500 + 3;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;
 
int n, m, l;
bitset<MAXN * MAXN> dp[MAXN], G, W, E;
string s;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> l;
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char c;
			cin >> c;
			G[i * m + j] = (c == '.');
			W[i * m + j] = E[i * m + j] = true;
		}
 
		W[i * m + m - 1] = false;
		E[i * m] = false;
	}
 
	cin >> s;
	s = "." + s;
	dp[0] = G;
	
	for (int i = 1; i <= l; i++) {
		int ind = i & 1;
		dp[ind].reset();
 
		if (s[i] == 'N' || s[i] == '?') dp[ind] |= (dp[1 - ind] >> m);
		if (s[i] == 'S' || s[i] == '?') dp[ind] |= (dp[1 - ind] << m);
		if (s[i] == 'E' || s[i] == '?') dp[ind] |= ((dp[1 - ind] << 1) & E);
		if (s[i] == 'W' || s[i] == '?') dp[ind] |= ((dp[1 - ind] >> 1) & W);
		dp[ind] &= G;
	}
 
	cout << dp[l & 1].count() << endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...