P6226 [BalticOI 2019] 潜艇 / Nautilus

Nostopathy · 2026-05-17 16:06:50 · 题解

这题上一道 P6225 就是著名的异或橙子，在做的时候好奇来看了一下这题，没想到这么好玩。

子任务 1

所有的方向都是固定的，意味着可以从每个合法位置开始，根据方向模拟，判断是否可行并统计。

时间复杂度 \Theta(RCM)。

子任务 2

发现本题的过程是有方向性的，每一步都可由上一步向某个方向走一格得到。自然想到 DP，设 f_{k,i,j} 为经过前 k 次操作，是否可能处于 (i,j) 位置。

得到转移方程：

• 若操作为 N，f_{k,i,j} \leftarrow f_{k-1,i+1,j}；
• 若操作为 S，f_{k,i,j} \leftarrow f_{k-1,i-1,j}；
• 若操作为 E，f_{k,i,j} \leftarrow f_{k-1,i,j-1}；
• 若操作为 W，f_{k,i,j} \leftarrow f_{k-1,i,j+1}；
• 若操作为 ?，f_{k,i,j} 取对上面四种情况进行 or 的结果。

时间复杂度 \Theta(RCM)，数组可以压掉 k 这一维。

子任务 3

延续子任务 2 做法，考虑优化转移。发现当进行一次操作时，上一步的所有情况都需要进行操作，f 的值都进行了移动。又因为只有 0,1 两种状态，考虑使用 bitset 优化。

将二维数组 f 压成一维，每次转移就可以利用位运算中的左移、右移、按位与、按位或操作。例如，原本 N 操作的转移就可以写为 f >> c，W 操作写为 f >> 1 等。注意边界。

时间复杂度 \Theta(\frac{RCM}{w})，空间复杂度 \Theta(\frac{RC}{w})，其中 w 为机器位数。

正解代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 505;

int r, c, m;
string s;
bitset<N * N> ok, w, e, f;

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

    cin >> r >> c >> m;
    for(int i = 1; i <= r; ++ i) // 读入，处理是否合法的状态，方便转移
        for(int j = 1; j <= c; ++ j){
            char ch;
            cin >> ch;
            int p = (i - 1) * c + j;
            if(ch == '.') ok[p] = 1;
            if(j != 1) e[p] = 1;
            if(j != c) w[p] = 1; 
        }
    cin >> s;
    f = ok;
    for(int i = 0; i < m; ++ i){ // 利用位运算转移
        if(s[i] == 'N') f = (f >> c) & ok;
        if(s[i] == 'S') f = (f << c) & ok;
        if(s[i] == 'W') f = (f >> 1) & ok & w;
        if(s[i] == 'E') f = (f << 1) & ok & e;
        if(s[i] == '?') f = ((f >> c) | (f << c) | ((f >> 1) & w) | ((f << 1) & e)) & ok;
    }
    cout << f.count(); // 输出 1 的个数

    return 0;
}