娱乐 奇怪的算法挑战【第①期】拼图游戏

[Mr.K 018]

  对矩阵的可能形状做了一些观察，又参考了yhz的回复，以下是目前为止观察得出的结果。如果一个仅由0和1为元素的n阶方阵合题意，那么它必须：

1）是沿副对角线对称的，前面不少人都发现了；

2）左上三角形要么只有一个连通分量，要么只有两个连通分量。若有两个：

2.1）这两个连通分量必须各自占据一些处在边线（左或上）和反对角线上的元素，否则整个矩阵就会出现多于2个的连通分量。进而得知，

2.2）右上方元素和左下方元素分属不同的连通分量；

2.3）参考yhz的回复，边线上0和1只能翻转一次；

2.4）反对角线上0和1也只能翻转一次。如果翻转了多于1次（例如3次。参考2.2，不可能翻转偶数次），就会破坏原有两个连通分量的连通性，形如

0 1 1 1 1 1
0 1 1 0 1
0 1 1 0
0 1 1
0 0
0

上述几个要求只是必要条件，并非充分条件，例如，将上例（4，3）处的1换为0可以使得矩阵满足上述五个条件，但仍不合题意。

 

从另一种角度考虑，合题意的矩阵，一定存在某种分割线分割开其左上三角，一段位于反对角线、另一端位于上或左边线，且其一侧均为0，另一侧均为1。

但诡谲的是，这个分割线如果从对角线出发的话，是可以向下甚至向右行进的