This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
const int nax = 501;
char grid[nax][nax];
vector<vector<int>>dp_new(nax, vector<int>(nax, 0));
vector<vector<int>>dp_old(nax, vector<int>(nax, 0));
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> grid[i][j];
}
}
string s;
cin >> s;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
dp_old[i][j] = (grid[i][j] == '.' ? 1 : 0);
}
}
for (int t = 1; t <= k; t++){
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (grid[i][j] == '#')continue;
if (s[t - 1] == 'N' || s[t - 1] == '?'){
if (i)dp_new[i][j] |= dp_old[i - 1][j];
}
if (s[t - 1] == 'S' || s[t - 1] == '?'){
if (i != n - 1)dp_new[i][j] |= dp_old[i + 1][j];
}
if (s[t - 1] == 'E' || s[t - 1] == '?'){
if (j)dp_new[i][j] |= dp_old[i][j - 1];
}
if (s[t - 1] == 'W' || s[t - 1] == '?'){
if (j != m - 1){
dp_new[i][j] |= dp_old[i][j + 1];
}
}
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
dp_old[i][j] = dp_new[i][j];
dp_new[i][j] = 0;
}
}
}
int ans = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
ans += dp_old[i][j];
}
}
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |