Submission #492997

#TimeUsernameProblemLanguageResultExecution timeMemory
492997Haruto810198Nautilus (BOI19_nautilus)C++17
66 / 100
1084 ms1228 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 510;

int r, c, m;
string str;
bool arr[MAX][MAX];
bool dp[MAX][MAX], newdp[MAX][MAX];
int res;

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>r>>c>>m;
	FOR(i, 1, r, 1){
		FOR(j, 1, c, 1){
			char ch;
			cin>>ch;
			if(ch == '.') dp[i][j] = arr[i][j] = 1;
		}
	}

	cin>>str;
	for(char i : str){
		
		vector<pii> dd;
		
		if(i == 'W') dd.eb(0, -1);
		if(i == 'E') dd.eb(0, 1);
		if(i == 'N') dd.eb(-1, 0);
		if(i == 'S') dd.eb(1, 0);
		if(i == '?'){
			dd.eb(0, -1);
			dd.eb(0, 1);
			dd.eb(-1, 0);
			dd.eb(1, 0);
		}
		
		FOR(i, 1, r, 1){
			FOR(j, 1, c, 1){
				newdp[i][j] = 0;
			}
		}

		FOR(i, 1, r, 1){
			FOR(j, 1, c, 1){
				if(dp[i][j] == 0) continue;
				for(pii d : dd){
					int ii = i + d.F, jj = j + d.S;
					if(arr[ii][jj] == 1) newdp[ii][jj] = 1;
				}
			}
		}

		FOR(i, 1, r, 1){
			FOR(j, 1, c, 1){
				dp[i][j] = newdp[i][j];
			}
		}
		
	}

	FOR(i, 1, r, 1){
		FOR(j, 1, c, 1){
			res += dp[i][j];
		}
	}

	cout<<res<<'\n';
	
	return 0;

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...