제출 #485923

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

using namespace std;

const int N = 5e2 + 9;
const int M = 5e3 + 9;

bitset <N> dp[N][M], good[N];

int main () {
	int r, c, m;
	cin >> r >> c >> m;
	
	for (int i = 1; i <= r; i++) {
		for (int j = c; j >= 1; j--) {
			char x;
			cin >> x;
			
			dp[i][0][j] = good[i][j] = (x == '.');
		}
	}
	
	string s;
	cin >> s;
	s = "#" + s;
	
	for (int t = 1; t <= m; t++) {
		for (int i = 1; i <= r; i++) {
			if (s[t] == 'N') 
				dp[i][t] = dp[i + 1][t - 1] & good[i];
			
			if (s[t] == 'W')
				dp[i][t] = (dp[i][t - 1] << 1) & good[i];
				
			if (s[t] == '?')
				dp[i][t] = (dp[i + 1][t - 1] | dp[i - 1][t - 1] | (dp[i][t - 1] << 1) | (dp[i][t - 1] >> 1)) & good[i];
		
			if (s[t] == 'S')
				dp[i][t] = dp[i - 1][t - 1] & good[i];
				
			if (s[t] == 'E')
				dp[i][t] = (dp[i][t - 1] >> 1) & good[i];
				
		}
	}
	
	int res = 0;
	for (int i = 1; i <= r; i++)
		res += dp[i][m].count();
	
	cout << res << "\n";
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...