1.状态简化

维护村子的四个角落等价于维护整个村子。

证明如下

必要性 ：

整个村子合法，则四个角落合法

充分性 ：

将村子分成四块。

若村子四个角落 $(x, y)$ 合法，则其周围三块区域也合法（降雨相同），所以村子所分四块皆合法。

2.记忆化搜索

1. 确定状态

云的位置、四个角落的降雨情况、当前天数。

2. 满足条件

所以状态相等

3. 作用

将搜索树看作一个图，则此图的同一节点只用遍历一次，也就是一个 $dag$ (有向无环图)。

3.常数优化

1. 方式

布尔关系可用二进制表示。

2. 优化状态

云的位置、四个角落的降雨情况、村庄规划。

3. 优化

a | b       // a 和 b 的并集，用于求云的二进制表示（将其所在四块区域取并即可）
a & b       // a 和 b 是否有交集, 用于判断降雨和村庄规划是否冲突
a | 1 << b  // 将 a 二进制表示的第 b 位置为 1, 用于二进制的转换