Submission #213562

#TimeUsernameProblemLanguageResultExecution timeMemory
213562usachevd0Nautilus (BOI19_nautilus)C++14
66 / 100
1083 ms1280 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back #define all(a) (a).begin(), (a).end() typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef long double ld; template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; } template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; } void debug_out() { cerr << endl; } template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); } #ifdef DEBUG #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif const int maxN = 502; int n, m, k; bool grid[maxN][maxN]; bool dp[2][maxN][maxN]; int dx[256], dy[256]; bool valid(int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; } signed main() { #ifdef DEBUG freopen("in", "r", stdin); #endif ios::sync_with_stdio(0); cin.tie(0); dx['N'] = 1; dy['N'] = 0; dx['S'] = -1; dy['S'] = 0; dx['W'] = 0; dy['W'] = 1; dx['E'] = 0; dy['E'] = -1; cin >> n >> m >> k; for (int i = 0; i < n; ++i) { string s; cin >> s; for (int j = 0; j < m; ++j) { grid[i][j] = s[j] == '.'; } } memcpy(dp[0], grid, sizeof(grid)); string I; cin >> I; for (int l = 1; l <= k; ++l) { char c = I[l - 1]; memset(dp[l & 1], 0, sizeof(dp[l & 1])); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (!grid[i][j]) continue; if (c != '?') { int x = i + dx[c]; int y = j + dy[c]; if (valid(x, y) && grid[x][y] && dp[l & 1 ^ 1][x][y]) { dp[l & 1][i][j] = true; } } else { for (char _c : {'N', 'S', 'W', 'E'}) { int x = i + dx[_c]; int y = j + dy[_c]; if (valid(x, y) && grid[x][y] && dp[l & 1 ^ 1][x][y]) { dp[l & 1][i][j] = true; } } } } } } int ans = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (dp[k & 1][i][j]) ++ans; cout << ans << '\n'; return 0; }

Compilation message (stderr)

nautilus.cpp: In function 'int main()':
nautilus.cpp:90:37: warning: array subscript has type 'char' [-Wchar-subscripts]
                     int x = i + dx[c];
                                     ^
nautilus.cpp:91:37: warning: array subscript has type 'char' [-Wchar-subscripts]
                     int y = j + dy[c];
                                     ^
nautilus.cpp:92:59: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
                     if (valid(x, y) && grid[x][y] && dp[l & 1 ^ 1][x][y])
                                                         ~~^~~
nautilus.cpp:101:42: warning: array subscript has type 'char' [-Wchar-subscripts]
                         int x = i + dx[_c];
                                          ^
nautilus.cpp:102:42: warning: array subscript has type 'char' [-Wchar-subscripts]
                         int y = j + dy[_c];
                                          ^
nautilus.cpp:103:63: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
                         if (valid(x, y) && grid[x][y] && dp[l & 1 ^ 1][x][y])
                                                             ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...