Submission #609400

#	Time	Username	Problem	Language	Result	Execution time	Memory
609400		l_reho	Nautilus (BOI19_nautilus)	C++14	66 / 100	39 ms	9888 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;


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++){
			for(int k = 0; k <= M; k++) dp[i][j][k] = 0;
		}
	}
	
	
	
	for(int k = 0; k <= M; k++){
		for(int i = 0; i < R; i++){
			
			for(int j = 0; j < C; j++){
				if(mp[i][j] == '#') continue;	
				if(k == 0){
					
					if(S[k] == 'W')
						dp[i][j][k] = j-1 >= 0 && mp[i][j-1] != '#';
					
					if(S[k] == 'E')
						dp[i][j][k] = j+1 < C && mp[i][j+1] != '#';
					
					if(S[k] == 'S')
						dp[i][j][k] = i+1 < R && mp[i+1][j] != '#';
					
					if(S[k] == 'N')
						dp[i][j][k] = i-1 >= 0 && mp[i-1][j] != '#';
					
					if(S[k] == '?'){
						
						for(int d = 0; d < 4; d++){
							int ni = i+dirs[d][0];
							int nj = j+dirs[d][1];
							if(ni < 0 || ni >= R || nj < 0 || nj >= C || mp[ni][nj] == '#') continue;
							dp[i][j][k] |= 1;
						}
						
					}	
					
					continue;
				}
				
				if(S[k-1] == 'W')
					dp[i][j][k] = j+1 < C && mp[i][j+1] != '#' && dp[i][j+1][k-1];
				
				if(S[k-1] == 'E')
					dp[i][j][k] = j-1 >= 0 && mp[i][j-1] != '#' && dp[i][j-1][k-1];
				
				if(S[k-1] == 'S')
					dp[i][j][k] = i-1 >= 0 && mp[i-1][j] != '#' && dp[i-1][j][k-1];
				
				if(S[k-1] == 'N')
					dp[i][j][k] = i+1 < R && mp[i+1][j] != '#' && dp[i+1][j][k-1];
				
				if(S[k-1] == '?'){
					
					for(int d = 0; d < 4; d++){
						int ni = i+dirs[d][0];
						int nj = j+dirs[d][1];
						if(ni < 0 || ni >= R || nj < 0 || nj >= C || mp[ni][nj] == '#') continue;
						dp[i][j][k] |= dp[ni][nj][k-1];
					}
					
				}
			}
			
		}
	}
	
	
	for(int i = 0; i < R; i++){
		for(int j = 0; j < C; j++){
			if(dp[i][j][M] == 1){
				ans++;
			}			
		}
	}
	
	cout<<ans<<endl;
	
}
 
int main(){
	solve();
	return 0;
}

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