BalticOI 2019 Day1 T2. Nautilus 题解

题目大意

给定一个 $R \times C$ 的网格地图，其中 # 表示岛屿，. 表示水域。潜艇只能在水域中航行。监听者收到了 $M$ 分钟的潜艇移动信号，信号由 N(北)、E(东)、S(南)、W(西)、?(未知) 组成。需要计算潜艇当前可能的位置数量。

算法思路

核心思想：位集优化动态规划

本题使用 位集（Bitset） 来高效处理大规模的状态转移，利用位级并行性大幅提升性能。

状态表示

• 使用 bitset<510*510> 表示状态，每个 bit 代表网格中的一个位置
• f[pos] = 1 表示潜艇可能位于该位置
• 初始状态：所有水域位置都可能存在潜艇

关键技术

1. 坐标编码

int p(int x, int y) {
    return m * (x - 1) + y;
}

将二维坐标 $(x,y)$ 映射为一维索引，便于位集操作。

2. 边界处理掩码

• mpe：屏蔽最左列，防止向西移动越界
• mpw：屏蔽最右列，防止向东移动越界
• mp：屏蔽岛屿位置，确保只在水域移动

3. 移动的位运算实现

// 不确定方向：四个方向都可能
f = ((f << m) | (f >> m) | ((f << 1)&mpe) | ((f >> 1)&mpw)) & mp;

// 确定方向：单方向移动
f = (f >> m) & mp;  // 北(N)
f = (f << m) & mp;  // 南(S)  
f = (f << 1) & mp & mpe;  // 东(E)
f = (f >> 1) & mp & mpw;  // 西(W)

算法流程

1. 初始化

   • 读取地图，标记所有水域位置
   • 设置边界掩码
   • 初始状态 f 包含所有水域位置

2. 处理移动信号

   • 对于每个信号字符：
     • 如果是 ?：向四个方向扩展可能位置
     • 如果是确定方向：向指定方向移动
   • 每次移动后与水域掩码 mp 取交集

3. 输出结果

   • 最终 f.count() 即为可能的位置数量

复杂度分析

• 时间复杂度：$O(M \times \frac{R \times C}{w})$，其中 $w$ 是机器字长（通常64）
• 空间复杂度：$O(R \times C)$
• 相比普通DP的 $O(M \times R \times C)$，性能提升显著

代码详解

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

const int N = 510;
char a[N][N], M[5010];
bitset<510*510> f, mp, mpe, mpw;
int n, m, K;

// 坐标编码函数
int p(int x, int y) { return m * (x - 1) + y; }

int main() {
    cin >> n >> m >> K;
    
    // 初始化边界掩码
    mpe.set(); mpw.set();
    
    // 读取地图并设置水域位置
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
            if(a[i][j] == '.') 
                mp[p(i,j)] = f[p(i,j)] = 1;
            // 设置边界掩码
            if(j == 1) mpe[p(i,j)] = 0;
            if(j == m) mpw[p(i,j)] = 0;
        }
    
    // 读取移动信号
    scanf("%s", M + 1);
    
    // 处理每个移动信号
    for(int i = 1; i <= K; i++) {
        char c = M[i];
        if(c == '?') {
            // 不确定方向：四个方向都可能
            f = ((f << m) | (f >> m) | ((f << 1)&mpe) | ((f >> 1)&mpw)) & mp;
        } else {
            // 确定方向移动
            if(c == 'N') f = (f >> m) & mp;
            if(c == 'S') f = (f << m) & mp;
            if(c == 'E') f = (f << 1) & mp & mpe;
            if(c == 'W') f = (f >> 1) & mp & mpw;
        }
    }
    
    cout << f.count() << endl;
    return 0;
}

样例分析

样例1

输入：
5 9 7
...##....
..#.##..#
..#....##
.##...#..
....#....
WS?EE??

输出：22

解释：经过7次移动后，潜艇可能位于22个不同的水域位置。

总结

本题展示了位集在状态压缩DP中的强大应用：

• 利用位级并行性处理大规模状态
• 通过位运算高效实现状态转移
• 边界处理通过掩码机制优雅解决

这种优化技巧在解决大规模网格搜索问题时非常有效，特别是在状态可以表示为布尔值且转移规则简单的情况下。