Submission #1307966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307966		shisp1	Nautilus (BOI19_nautilus)	C++20	66 / 100	8 ms	1664 KiB

nautilus

#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;
}

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