제출 #673857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
673857		Duy_e	Nautilus (BOI19_nautilus)	C++14	100 / 100	205 ms	158272 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';
    }
};

namespace sub3 { // using bitset to speed up dp
    const long long Max = 5e3 + 5;
    bitset <N> sea[N], dp[N][Max];

    void init() {
        rep(i, 1, R) rep(j, 1, C) if (a[i][j] == '.') 
            sea[i].set(j);

        // init each row of the sea
    }

    string direction = "WESN";

    void solve() {
       
        // E, W move in the same row -> (>> 1) or (<< 1)
        init();
        rep(i, 1, R) 
            dp[i][0] = sea[i];

        rep(t, 0, M - 1) {
            for (char ch: direction) if (ch == s[t] || s[t] == '?') {
                rep(i, 1, R) {
                    if (ch == 'W')
                        dp[i][t + 1] |= (dp[i][t] >> 1) & sea[i];
                    
                    if (ch == 'E')
                        dp[i][t + 1] |= (dp[i][t] << 1) & sea[i];

                    if (ch == 'S')
                        dp[i + 1][t + 1] |= dp[i][t] & sea[i + 1];
                    
                    if (ch == 'N')
                        dp[i - 1][t + 1] |= dp[i][t] & sea[i - 1];
                }
            }
        }

        ll ans = 0;
        rep(i, 1, R) ans += dp[i][M].count();

        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;
    // if (M <= 500)
    //     sub12 :: solve();
    // else 
    sub3 :: solve();
    return 0;
}  

컴파일 시 표준 에러 (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: 34 / 34