Submission #221342

#TimeUsernameProblemLanguageResultExecution timeMemory
221342Leonardo_PaesNautilus (BOI19_nautilus)C++17
66 / 100
46 ms12412 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 110; int r, c, m, ans; int dp[maxn][maxn][maxn], mat[maxn][maxn], mark[maxn][maxn]; int ih[] = {-1, +1, 0, 0}; int jh[] = {0, 0, +1, -1}; string s; map<char, int> mp; int solve(int i, int j, int pos){ if(pos == (int)s.size()) return mark[i][j] = 1; if(dp[i][j][pos] != -1) return dp[i][j][pos]; int tot = 0; if(s[pos] == '?'){ for(int k=0; k<4; k++){ int newi = i + ih[k], newj = j + jh[k]; if(newi >= 1 and newi <= r and newj >= 1 and newj <= c and mat[newi][newj]){ tot |= solve(newi, newj, pos+1); } } } else{ int newi = i + ih[mp[s[pos]]], newj = j + jh[mp[s[pos]]]; if(newi >= 1 and newi <= r and newj >= 1 and newj <= c and mat[newi][newj]){ tot |= solve(newi, newj, pos+1); } } return dp[i][j][pos] = tot; } int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); cin >> r >> c >> m; for(int i=1; i<=r; i++){ for(int j=1; j<=c; j++){ char a; cin >> a; if(a == '.') mat[i][j] = 1; } } cin >> s; mp['N'] = 0; mp['S'] = 1; mp['E'] = 2; mp['W'] = 3; memset(dp, -1, sizeof dp); int ans = 0; for(int i=1; i<=r; i++){ for(int j=1; j<=c; j++){ if(mat[i][j]) solve(i, j, 0); } } for(int i=1; i<=r; i++){ for(int j=1; j<=c; j++){ ans += mark[i][j]; } } cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...