小游戏

KSJ大约 1 分钟

今天偶然看到一个广告，其上是一个小游戏，给定一个初始的围棋棋盘（被白棋占满），给定最终棋局，有两种操作，将一行变为白棋、一列变为黑棋。变为最终棋局就算获胜。

感觉有点意思，就给抽象为了如下规则

求合法操作序列（无解输出-1）

抽象化

若 $a_{i j} = 0$ 则显然进行了 $r_{i}$ ，且 $r_{i}$ 在 $c_{j}$ 之后，记作 $r_{i} & c_{j} \to r_{i}$
若 $a_{i j} = 1$ 则 $c_{j} & r_{i} \to c_{j}$

设Q为任意操作的组合，则显然有

$r_{i} Q r_{i} = Q r_{i}$ (第i行状态一致，且r_i不改变其它位置的状态)

同理 $c_{j} Q c_{j} = Q c_{j}$

所以之多有2n个等价的操作序列( $r_{1}, r_{2}, . . ., r_{n}, c_{1}, . . ., c_{n}$ )

又检查 $a_{11}, a_{22}, . . ., a_{n n}$ 的取值即可对所有2n个操作连边，故最终得到一个图，显然可行解就对应着拓扑序（没有则无解）

~~先空着~~