小游戏

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

---

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

1. 给定01矩阵 target[n][n]和初始0矩阵table[n][n]
2. op1 : 将一行变为1
3. op2 : 将列变为0

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

抽象化

1. 将 op1 记作 $r_i$ (指定第i行)
2. op2 记作 $c_j$ (指定第j列)

• 若 $a_{ij}=0$ 则显然 进行了 $r_i$，且$r_i$在$c_j$之后，记作$r_i \& c_j \to r_i$
• 若 $a_{ij}=1$则$c_j \& r_i \to c_j$

推论

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

$r_iQr_i=Qr_i$ (第i行状态一致，且r_i不改变其它位置的状态)

同理$c_jQc_j=Qc_j$

所以之多有2n个等价的操作序列($r_1,r_2,...,r_n,c_1,...,c_n$)

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

参考代码

先空着