方格取数问题 / 王者之剑
可以发现，相互限制的格子的横纵坐标之和肯定是一个奇数和一个偶数。即横纵坐标之和奇偶性相同的格子之间一定不会限制。因此若我们将限制关系以边的形式表达，那么形成的图为一个二分图。
考虑令横纵坐标之和为奇数的格子为左部点，偶数的为右部点；分别对应 \(S, T\) 集合。令左部点不在 \(S\) 集合中表示不选择，右部点不在 \(T\) 集合中表示不选择。
那么对于一对限制的格子，可以考虑从横纵坐标之和为奇数的格子向横纵坐标之和为偶数的格子连一条容量为 \(\infty\) 的边。
那么也就是说源点连向奇数的格子的边和偶数的格子连向汇点的边中一定有一条被割掉，即两个格子不会同时选择，限制成立，求最小割即可。
骑士共存问题
同 方格取数问题 / 王者之剑，我们可以发现可以相互攻击到的格子肯定是一个奇数和一个偶数。
那么可以使用与上述题目相同的方法去处理可以相互攻击到的格子。
对于限制不能使用的格子，若其横纵坐标之和为奇数，那么可以从其连一条向汇点，容量为 \(\infty\) 的边，因此源点连向这个点的边一定会被割掉，进而确保其一定不会被选择。对于横纵坐标之和为偶数的节点同理。