# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
947595 | 2024-03-16T14:28:32 Z | VMaksimoski008 | Nautilus (BOI19_nautilus) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("0fast") using namespace std; int32_t main() { int n, m, K, ans = 0; cin >> n >> m >> K; char mat[n][m]; for(int i=0; i<n; i++) for(int j=0; j<m; j++) cin >> mat[i][j]; string s; cin >> s; s = "." + s; bool dp[2][n][m]; memset(dp, 0, sizeof(dp)); for(int i=0; i<n; i++) for(int j=0; j<m; j++) dp[0][i][j] = (mat[i][j] == '.'); for(int i=1; i<=K; i++) { for(int r=0; r<n; r++) { for(int c=0; c<m; c++) { dp[1][r][c] = 0; if(mat[r][c] == '#') continue; if((s[i] == 'W' || s[i] == '?') && c + 1 < m && dp[0][r][c+1]) dp[1][r][c] = 1; if((s[i] == 'E' || s[i] == '?') && c - 1 >= 0 && dp[0][r][c-1]) dp[1][r][c] = 1; if((s[i] == 'N' || s[i] == '?') && r + 1 < n && dp[0][r+1][c]) dp[1][r][c] = 1; if((s[i] == 'S' || s[i] == '?') && r - 1 >= 0 && dp[0][r-1][c]) dp[1][r][c] = 1; } } for(int r=0; r<n; r++) for(int c=0; c<m; c++) dp[0][r][c] = dp[1][r][c]; } for(int i=0; i<n; i++) for(int j=0; j<m; j++) ans += dp[0][i][j]; cout << ans << '\n'; return 0; }