Submission #180282

#TimeUsernameProblemLanguageResultExecution timeMemory
180282sochoNautilus (BOI19_nautilus)C++14
66 / 100
1040 ms888 KiB
#include "bits/stdc++.h" using namespace std; int a, b, m; vector<vector<bool> > grid; string s; bool valid(int x, int y) { // cout << "! " << x << ' ' << y << endl; if (x < 0 || y < 0) return false; if (x >= a || y >= b) return false; return grid[x][y]; } int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; int main() { cin >> a >> b >> m; for (int i=0; i<a; i++) { string s; cin >> s; vector<bool> tr(b); for (int j=0; j<b; j++) { tr[j] = (s[j] == '.'); } grid.push_back(tr); } cin >> s; s = ' ' + s; bool reach[a][b][2]; memset(reach, 0, sizeof reach); for (int i=0; i<a; i++) { for (int j=0; j<b; j++) { reach[i][j][0] = valid(i, j); } } for (int STEP=1; STEP<=m; STEP++) { // ith step char st = s[STEP]; for (int i=0; i<a; i++) { for (int j=0; j<b; j++) { if (valid(i, j)) { if (st == 'W') { reach[i][j][STEP%2] = (valid(i, j+1) && reach[i][j+1][(STEP+1)%2]); } else if (st == 'E') { reach[i][j][STEP%2] = (valid(i, j-1) && reach[i][j-1][(STEP+1)%2]); } else if (st == 'N') { reach[i][j][STEP%2] = (valid(i+1, j) && reach[i+1][j][(STEP+1)%2]); } else if (st == 'S') { reach[i][j][STEP%2] = (valid(i-1, j) && reach[i-1][j][(STEP+1)%2]); } else { reach[i][j][STEP%2] = false; for (int k=0; k<4; k++) { reach[i][j][STEP%2] |= (valid(i+dx[k], j+dy[k]) && reach[i+dx[k]][j+dy[k]][(STEP+1)%2]); } } } else { reach[i][j][STEP%2] = false; } } } } int c = 0; for (int i=0; i<a; i++) { for (int j=0; j<b; j++) { if (reach[i][j][m%2]) c++; } } cout << c << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...