状态模拟

一句话理解

状态模拟：把当前局面压成一个状态，按转移走。

为什么要学

开关灯、魔方小面、二进制开关。

讲解

先定义状态是什么：例如 n 个灯的开灭用一个 0..2^n-1 的整数。再定义一步会变成哪个状态。

状态少可以用 vis 数组或 BFS。

例子

3 个灯，状态 0 到 7。按第 i 个开关就异或 (1<<i)。

常见错误

• 状态定义含糊，转移写重或写漏。
• 状态很多却 vis 开成 int 爆内存。