Submission #673841

#	Time	Username	Problem	Language	Result	Execution time	Memory
673841		Duy_e	Nautilus (BOI19_nautilus)	C++17	66 / 100	1095 ms	128680 KiB

nautilus

#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define st first
#define nd second
#define file "test"
#define rep(i, begin, end) for (ll i = (begin); i <= (end); i ++)
#define rrep(i, begin, end) for (ll i = (begin); i >= (end); i --)
using namespace std;
const long long INF = 1e18;
const long long N = 500 + 5;

char a[N][N];
string s;
int R, C, M;

struct node {
    int x, y, i;
    node(int _x, int _y, int _i) {
        x = _x; y = _y; i = _i;
    }

    bool legal() {
        return x >= 1 && x <= R && y >= 1 && y <= C && i <= M && a[x][y] == '.';
    }
};


namespace sub12 {
    
    int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
    int dir[300];

    bool dp[N][N][N];

    void init() {
        dir['N'] = 0;
        dir['S'] = 1;
        dir['E'] = 3;
        dir['W'] = 2; 
        dir['?'] = -1;
    }

    node nxt(node x, char ch) {
        int d = dir[ch];
        x.x += dr[d];
        x.y += dc[d];
        x.i ++;
        return x;
    }

    void solve() {
        init();
        queue <node> q;
        
        string direction = "WENS";

        rep(i, 1, R) rep(j, 1, C) if (a[i][j] == '.')
            q.push(node(i, j, 0)), dp[i][j][0] = 1;

        while (q.size()) {
            node u = q.front(); q.pop();
            if (u.i == M) continue;

            char ch = s[u.i];
            for (char x: direction) if (ch == '?' || x == ch) {
                node v = nxt(u, x);
                if (v.legal()) {
                    if (!dp[v.x][v.y][v.i]) {
                        dp[v.x][v.y][v.i] = true;
                        q.push(v);
                    }
                }
            }
        }

        int ans = 0;
        rep(i, 1, R) rep(j, 1, C) if (dp[i][j][M]) ans ++;
    
        cout << ans << '\n';
    }
};

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    // #endif
    
    cin >> R >> C >> M;

    rep(i, 1, R) rep(j, 1, C) 
        cin >> a[i][j];

    cin >> s;
    sub12 :: solve();
    return 0;
}  

Compilation message (stderr)

nautilus.cpp: In function 'node sub12::nxt(node, char)':
nautilus.cpp:45:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   45 |         int d = dir[ch];
      |                     ^~

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