Submission #1367108

#TimeUsernameProblemLanguageResultExecution timeMemory
1367108gvancakNautilus (BOI19_nautilus)C++20
66 / 100
1095 ms59388 KiB
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll int
using namespace std;
const ll N=505,INF=1e12;
ll ans,c[N],b[N][N],n,k,m,q;
char a[N][N];
bool ok;
vector < pair<ll,ll> > v;
vector <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;
	for (int o=0; o<d[i1][j1].size(); o++){
		if (d[i1][j1][o]==k) return 0;
	}
	d[i1][j1].pb(k);
	if (a[i1][j1]!='.') return 0;
	int x=i1,y=j1;
	if (k==s.size()) {
		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;
}
signed 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];
		}
	}
	cin >> s;
	pair <ll,ll> g;
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++){
			
			ok=check(i,j,0);	
		}
	}
	ans=v.size();
	cout << ans << endl;


}

Compilation message (stderr)

nautilus.cpp:8:20: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+12' to '2147483647' [-Woverflow]
    8 | const ll N=505,INF=1e12;
      |                    ^~~~
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...