Submission #921420

#TimeUsernameProblemLanguageResultExecution timeMemory
921420aykhnNautilus (BOI19_nautilus)C++17
66 / 100
1030 ms4440 KiB
#include <bits/stdc++.h> // author: aykhn using namespace std; #define int long long #define inf 0x3F3F3F3F const int MXN = 5e2 + 5; int n, m, K; char mat[MXN][MXN]; string s; int A[4] = {0, 0, -1, 1}; int B[4] = {-1, 1, 0, 0}; int C[26], D[26]; signed main() { ios_base::sync_with_stdio(0); cin.tie(nullptr); C['S' - 'A'] = -1; D['S' - 'A'] = 0; C['N' - 'A'] = 1; D['N' - 'A'] = 0; C['W' - 'A'] = 0; D['W' - 'A'] = 1; C['E' - 'A'] = 0; D['E' - 'A'] = -1; cin >> n >> m >> K; vector<vector<int>> dp(n, vector<int> (m, 0)), ndp; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> mat[i][j]; dp[i][j] = (mat[i][j] != '#'); } } cin >> s; s = "#" + s; int res; for (int k = 1; k <= K; k++) { ndp.assign(n, vector<int> (m, 0)); res = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (mat[i][j] == '#') continue; if (s[k] == '?') { for (int l = 0; l < 4; l++) { int x = i + A[l], y = j + B[l]; if (x >= 0 && x < n && y >= 0 && y < m) ndp[i][j] |= dp[x][y]; } } else { int x = i + C[s[k] - 'A'], y = j + D[s[k] - 'A']; if (x >= 0 && x < n && y >= 0 && y < m) ndp[i][j] |= dp[x][y]; } res += ndp[i][j]; } } dp = ndp; } cout << res << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...