| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 202660 | 2020-02-17T16:37:01 Z | stefdasca | Nautilus (BOI19_nautilus) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("Ofast")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9
// #define fisier 1
using namespace std;
typedef long long ll;
int n, m, k;
string s;
char mat[502][502];
bitset<502> dp[5002][502];
int main()
{
#ifdef fisier
ifstream f("input.in");
ofstream g("output.out");
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> k;
for(int i = 0; i < n; ++i)
cin >> mat[i];
cin >> s;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if(mat[i][j] != '#')
dp[0][i][j] = 1;
for(int x = 0; x < k; ++x)
{
if(s[x] == 'E')
{
for(int i = 0; i < n; ++i)
for(int j = 0; j + 1 < m; ++j)
{
if(mat[i][j] == '#')
dp[x][i][j] = 0;
if(dp[x][i][j] == 0)
continue;
if(mat[i][j+1] != '#')
dp[x+1][i][j+1] = 1;
}
}
if(s[x] == 'W')
{
for(int i = 0; i < n; ++i)
for(int j = 1; j < m; ++j)
{
if(mat[i][j] == '#')
dp[x][i][j] = 0;
if(dp[x][i][j] == 0)
continue;
if(mat[i][j-1] != '#')
dp[x+1][i][j-1] = 1;
}
}
if(s[x] == 'N')
{
for(int i = 0; i + 1 < n; ++i)
dp[x+1][i] = dp[x][i+1];
}
if(s[x] == 'S')
{
for(int i = 1; i < n; ++i)
dp[x+1][i] = dp[x][i-1];
}
if(s[x] == '?')
{
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
{
if(mat[i][j] == '#')
dp[x][i][j] = 0;
if(dp[x][i][j] == 0)
continue;
if(j + 1 < m && mat[i][j+1] != '#')
dp[x+1][i][j+1] = 1;
if(i + 1 < n && mat[i+1][j] != '#')
dp[x+1][i+1][j] = 1;
if(j && mat[i][j-1] != '#')
dp[x+1][i][j-1] = 1;
if(i && mat[i-1][j] != '#')
dp[x+1][i-1][j] = 1;
}
}
}
int ans = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if(mat[k][i][j] != '#')
ans += dp[k][i][j];
cout << ans;
return 0;
}