# 一类四邻接网格图森林的匹配问题：位集补充方案

沿用出题人的累计位移去重与候选集合求交思想，Codex（GPT-6）给出按机器字处理的实现。[程序](alternative-bitsets.cpp)支持完整正式范围；[首选题解](solution.zh.md)给出共同的前缀合法性证明及列表方案。

## 平移后的道路掩码

按行保存道路位集 $R_r$ ，另有候选起点位集 $S_r$ ，初始 $S_r=R_r$ .若出现新的累计位移 $(x,y)$ ，起点行 $r$ 应与道路行 $r+x$ 比较：候选列 $c$ 只有在道路位 $R_{r+x}[c+y]$ 为一时才保留。

因此，从道路行中截取相应的连续机器字窗口，与候选字按位与。目标行越界时窗口为零。窗口跨两个源机器字时组合右移后的前一字及左移后的后一字；横向偏移为负时必须做向下取整的除法，不能误用向零截断。位移余数为零时单独处理，避免移位量等于字宽。初始候选位集只在网格内含一，字尾补位不会产生额外起点。

之后累加所有候选字中的一的个数。本实现采用标准无符号运算的分组位计数，不依赖编译器专用指令。重复位移直接输出上一次计数；集合为空或位移绝对值达到 $n$ 后答案永久为零。

## 正确性

每个候选位最终恰好等于“此前合法，并且当前位置为网格内道路”两个条件的逻辑与。它与逐个起点筛选完全相同。按位与永不重新加入已清除的位，故任何曾失败的起点都不会恢复。累计位移重复时没有新增条件，所以跳过筛选也正确。

## 复杂度与适用情况

令 $K$ 为真正执行的新位移筛选次数，$W$ 为机器字位数，本程序为六十四。每次需要 $n\lceil n/W\rceil$ 个窗口和按位与，总时间为
$$
O(n^2+m+K n\lceil n/W\rceil).
$$
由共同题解可知 $K\le n^2+1$ ，故也得到 $O(n^2+m+n^3\lceil n/W\rceil)$ 的一般界。位集空间为 $O(n\lceil n/W\rceil)$ 个机器字，另有 $O(n^2)$ 个位移访问标记。

当候选起点很多时，机器字并行可以减少检查次数；当候选很少但新位移很多时，仍要遍历整幅位集，列表通常更快。两种方法在完整正式数据上逐行核对，均纳入[性能校准](../../../docs/benchmark-R28.json)。