Submission #609217

#	Time	Username	Problem	Language	Result	Execution time	Memory
609217		l_reho	Nautilus (BOI19_nautilus)	C++14	0 / 100	15 ms	5332 KiB

nautilus

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long

int R, C, M;
vector<string> mp;
string S;
int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int dp[101][101][102];

bool vis[101][101][101];

int ans = 0;

int si, sj;

int solver(int i, int j, int k){
	if(k == M){
		dp[i][j][k] = 1;
		return 1;
	}
	
	if(dp[i][j][k] == 1) return 1;
	if(vis[i][j][k] == 1) return 0;
	vis[i][j][k] = true;
	// if(dp[i][j][k] == 0) return 0;
	 
	
	int ni = i;
	int nj = j;
	
	if(S[k] == 'W'){
		nj--;
		
		if(ni < 0 || ni >= R || nj < 0 || nj >= C || mp[ni][nj] == '#') return 0;
		
		
		if(solver(ni, nj, k+1)) dp[i][j][k] = 1;
		
	}else if(S[k] == 'E'){
		nj++;
		if(ni < 0 || ni >= R || nj < 0 || nj >= C || mp[ni][nj] == '#') return 0;
		
		if(solver(ni, nj, k+1)) dp[i][j][k] = 1;
	}else if(S[k] == 'S'){
		ni++;
		if(ni < 0 || ni >= R || nj < 0 || nj >= C || mp[ni][nj] == '#') return 0;
		
		if(solver(ni, nj, k+1)) dp[i][j][k] = 1;
	}else if(S[k] == 'N'){
		ni--;
		if(ni < 0 || ni >= R || nj < 0 || nj >= C || mp[ni][nj] == '#') return 0;
		
		if(solver(ni, nj, k+1)) dp[i][j][k] = 1;
	}else{	
		for(int d = 0; d < 4; d++){
			ni = i+dirs[d][0];
			nj = j+dirs[d][1];
			
			if(ni < 0 || ni >= R || nj < 0 || nj >= C || mp[ni][nj] == '#') continue;
		
			if(solver(ni, nj, k+1))
				dp[i][j][k] = 1;
			
		}		
	}
	
	// cout<<si<<" "<<sj<<" "<<" "<<i<<" "<<j<<" "<<dp[i][j][k]<<endl;
	
	return dp[i][j][k];
	
}

void solve(){
	cin>>R>>C>>M;
	
	mp.assign(R, "");
	
	for(string &s:mp) cin>>s;
	
	cin>>S;
	
	
	
	for(int i = 0; i < R; i++){
		for(int j = 0; j < C; j++){
			if(mp[i][j] == '#') continue;
			si = i;
			sj = j;
			
			solver(i, j, 0);
		}
	}
	
	
	for(int i = 0; i < R; i++){
		for(int j = 0; j < C; j++){
			for(int k = 0; k < M+1; k++){
				if(dp[i][j][k]){
					ans++;
					break;
				}
			}
		}
	}
	
	cout<<ans<<endl;
	
}
 
int main(){
	solve();
	return 0;
}

• Subtask 1: 0 / 29
• Subtask 2: 0 / 37
• Subtask 3: 0 / 34