oj.uz

Submission #609265

# Submission time Handle Problem Language Result Execution time Memory
609265 2022-07-27T13:04:50 Z l_reho Nautilus (BOI19_nautilus) C++14
29 / 100
 1000 ms 4348 KB 
#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;
	
	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++){
			if(dp[i][j][M]){
				ans++;
			}			
		}
	}
	
	cout<<ans<<endl;
	
}
 
int main(){
	solve();
	return 0;
}

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4308 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4308 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 23 ms 4348 KB Output is correct
8 Execution timed out 1092 ms 692 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4308 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 23 ms 4348 KB Output is correct
8 Execution timed out 1092 ms 692 KB Time limit exceeded
9 Halted 0 ms 0 KB -