Submission #1367188

#TimeUsernameProblemLanguageResultExecution timeMemory
1367188gvancakNautilus (BOI19_nautilus)C++20
66 / 100
1097 ms14596 KiB
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
using namespace std;
const ll N=505;
ll ans,c[N],b[N][N],n,k,m,q,mx;
char a[N][N];
bool ok;
vector < pair<ll,ll> > v,v1;
//set <int> d[N][N];
string s;
bool check(int i1,int j1,int k){
	if (i1<1 || i1>n || j1<1 || j1>m) return 0;
	if (a[i1][j1]!='.') return 0;
	int x=i1,y=j1;
	if (k==mx) {
		if (b[x][y]==0) v.pb(mp(x,y)); b[x][y]=1; return 1;
	}
	if (s[k]=='N') return check(x-1,y,k+1);
	if (s[k]=='S') return check(x+1,y,k+1);
	if (s[k]=='E') return check(x,y+1,k+1);
	if (s[k]=='W') return check(x,y-1,k+1);
	bool gg,ggg;
	if (s[k]=='?'){
		gg=check(x+1,y,k+1);
		if (gg==1) ggg=1;
	//	if (gg.f!=0) return gg;
		gg=check(x-1,y,k+1);
		if (gg==1) ggg=1;
	//	if (gg.f!=0) return gg;
		gg=check(x,y+1,k+1);
		if (gg==1) ggg=1;
	//	if (gg.f!=0) return gg;
		gg=check(x,y-1,k+1);
		if (gg==1) ggg=1;
	//	if (gg.f!=0) return gg;
		return ggg;
	}
	return 0;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    cin >> n >> m >> q;
    for (int i=1; i<=n; i++){
    	for (int j=1; j<=m; j++){
    		cin >> a[i][j];
    		if (a[i][j]=='.'){
    			v1.pb(mp(i,j));
			}
		}
	
	}
	cin >> s; int sz=0;
	for (int o=0; o<s.size(); o++){
	//	cout<<v1.size()<<endl;
		vector<pair<ll,ll> >().swap(v);
		for (int i=0; i<v1.size(); i++){
			mx=o+1;
			ok=check(v1[i].f,v1[i].s,o);
		//	cout<<v1[i].f<<" "<<v1[i].s<<" "<<v.size()<<endl;
		}
		vector<pair<ll,ll> >().swap(v1);
		for (int i=0; i<v.size(); i++) v1.pb(v[i]);
		for (int i=0; i<v.size(); i++) b[v[i].f][v[i].s]=0;
	}
	cout<<v.size()<<endl;


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