Submission #1307966

#TimeUsernameProblemLanguageResultExecution timeMemory
1307966shisp1Nautilus (BOI19_nautilus)C++20
66 / 100
8 ms1664 KiB
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define int long long
using namespace std;
const int mod = 1e9+7;
const ll inf = 1e18;
const int N = 110;
int n,m,t;
char a[105][105];
bool dp[105][105][105];

bool ok(int x,int y) {
    return x>=1 && x<=n && y>=1 && y<=m && a[x][y]!='#';
}

void solve() {
    memset(dp,0,sizeof(dp));
    cin >> n >> m >> t;
    for(int i = 1;i<=n;i++) {
        for(int j = 1;j<=m;j++) {
            cin >> a[i][j];
            if(a[i][j] != '#') {
                dp[i][j][0] = 1;
            }
        }
    }
    string s;
    cin >> s;
    for(int k = 1;k<=t;k++) {
        for(int i = 1;i<=n;i++) {
            for(int j = 1;j<=m;j++) {
                if(a[i][j] == '#') continue;
                if(s[k-1] == '?') {
                    if(ok(i,j-1)) dp[i][j][k] |= dp[i][j-1][k-1];
                    if(ok(i,j+1)) dp[i][j][k] |= dp[i][j+1][k-1];
                    if(ok(i-1,j)) dp[i][j][k] |= dp[i-1][j][k-1];
                    if(ok(i+1,j)) dp[i][j][k] |= dp[i+1][j][k-1];
                } else {
                    if(s[k-1] == 'S') {
                        if(ok(i-1,j)) dp[i][j][k] |= dp[i-1][j][k-1];
                    }
                    if(s[k-1] == 'N') {
                        if(ok(i+1,j)) dp[i][j][k] |= dp[i+1][j][k-1];
                    }
                    if(s[k-1] == 'E') {
                        if(ok(i,j-1)) dp[i][j][k] |= dp[i][j-1][k-1];
                    }
                    if(s[k-1] == 'W') {
                        if(ok(i,j+1)) dp[i][j][k] |= dp[i][j+1][k-1];
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i = 1;i<=n;i++) {
        for(int j = 1;j<=m;j++) {
            if(dp[i][j][t]) ans++;
        }
    }
    cout << ans << "\n";
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--) {
        solve();
    }





    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...