状态压缩

一句话理解

状态压缩：把局面塞进一个整数。

为什么要学

DP 或 BFS 的状态太离散时用位来编码。

讲解

n 个布尔量 → n 位。再加位置、步数等。状态总数要能开数组。

先估算 2^n * extra 的内存和时间。

例子

8 个棋子在不在用 8 位，再乘当前走到第几行。

常见错误

• 状态里塞进很大的坐标没离散化。
• 2^n 很大仍开 vis。