Submission #221342

#	Time	Username	Problem	Language	Result	Execution time	Memory
221342		Leonardo_Paes	Nautilus (BOI19_nautilus)	C++17	66 / 100	46 ms	12412 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

const int maxn = 110;

int r, c, m, ans;

int dp[maxn][maxn][maxn], mat[maxn][maxn], mark[maxn][maxn];

int ih[] = {-1, +1, 0, 0};
int jh[] = {0, 0, +1, -1};

string s;

map<char, int> mp;

int solve(int i, int j, int pos){
    if(pos == (int)s.size()) return mark[i][j] = 1;
    if(dp[i][j][pos] != -1) return dp[i][j][pos];

    int tot = 0;

    if(s[pos] == '?'){
        for(int k=0; k<4; k++){
            int newi = i + ih[k], newj = j + jh[k];

            if(newi >= 1 and newi <= r and newj >= 1 and newj <= c and mat[newi][newj]){
                tot |= solve(newi, newj, pos+1);
            }
        }
    }
    else{
        int newi = i + ih[mp[s[pos]]], newj = j + jh[mp[s[pos]]];

        if(newi >= 1 and newi <= r and newj >= 1 and newj <= c and mat[newi][newj]){
            tot |= solve(newi, newj, pos+1);
        }
    }

    return dp[i][j][pos] = tot;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    cin >> r >> c >> m;

    for(int i=1; i<=r; i++){
        for(int j=1; j<=c; j++){
            char a;

            cin >> a;

            if(a == '.') mat[i][j] = 1;
        }
    }

    cin >> s;

    mp['N'] = 0;
    mp['S'] = 1;
    mp['E'] = 2;
    mp['W'] = 3;

    memset(dp, -1, sizeof dp);

    int ans = 0;

    for(int i=1; i<=r; i++){
        for(int j=1; j<=c; j++){
            if(mat[i][j]) solve(i, j, 0);
        }
    }

    for(int i=1; i<=r; i++){
        for(int j=1; j<=c; j++){
            ans += mark[i][j];
        }
    }

    cout << ans << "\n";

    return 0;
}

• Subtask 1: 29 / 29
• Subtask 2: 37 / 37
• Subtask 3: 0 / 34