Submission #1344531

#TimeUsernameProblemLanguageResultExecution timeMemory
1344531aaaaaaaaNautilus (BOI19_nautilus)C++20
66 / 100
11 ms5236 KiB
#include <bits/stdc++.h>
using namespace std;

const int mxN = 105;

int dp[mxN][mxN][mxN];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M, K;
    cin >> N >> M >> K;

    string str;

    for(int i = 0; i < N; ++i){
        cin >> str;
        for(int j = 0; j < M; ++j){
            if(str[j] == '.') dp[i][j][0] = 1;
        }
    }

    cin >> str;

    auto relax = [&](int i, int j, int ni, int nj, int k) -> void {
        if(min(ni, nj) < 0 || ni >= N || nj >= M) return;
        if(dp[ni][nj][0]) dp[ni][nj][k + 1] |= dp[i][j][k];
    };

    for(int k = 0; k < K; ++k){
        for(int i = 0; i < N; ++i){
            for(int j = 0; j < M; ++j){
                if(dp[i][j][k]){
                    if(str[k] == '?'){
                        relax(i, j, i - 1, j, k);
                        relax(i, j, i + 1, j, k);
                        relax(i, j, i, j - 1, k);
                        relax(i, j, i, j + 1, k);
                    }else if(str[k] == 'W') {
                        relax(i, j, i, j - 1, k);
                    }else if(str[k] == 'N'){
                        relax(i, j, i - 1, j, k);
                    }else if(str[k] == 'S'){
                        relax(i, j, i + 1, j, k);
                    }else {
                        relax(i, j, i, j + 1, k);
                    }
                }
            }
        }
    }

    int ans = 0;

    for(int i = 0; i < N; ++i){
        for(int j = 0; j < M; ++j){
            ans += dp[i][j][K];
        }
    }

    cout << ans << "\n";

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