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

[yhz012]

想了下，可以理解为是问对于一个n * n的01矩阵，有多少种对称矩阵，使得0和1都是连续的吧？

 

假如说上面的理解是正确的，那大概就可以暴力递归了

首先1*1的只有0和1两个满足，因为实际上始终是对称的，我们不妨让右上角始终是0，然后最终结果乘2一下就好

接下来假设k*k的方案已经全部找到了，那么对于每种方案，接下来就是把这个方案放到右上角，然后左侧和最下面增加一行一列，使得增加的这一行一列对称并与原方案连续

 

要保证这个的话似乎可以用排除法？我大概需要仔细想一下。不过这么做完之后肯定能不重复，因为右上角部分就不重复，所以可以继续往下递归就行了

 

不对我傻了，这样会漏方案比如3*3的

1 0 0
0 0
1

这个是不连续的，但是在4*4的时候

1 1 0 0
1 0 0
1 1
1

是连续的

一月 9, 2021，由yhz012修改

[yhz012]

7 小时前, Muriya Tensei 说道:

从一侧分析的话，会导致另一侧的连续性难以判断，所以可以（）

因为是对称矩阵，所以如果带着（上）三角矩阵是联通的，那整个矩阵是联通的倒是没问题

不过我刚才想到仅仅要求联通应该是不够的

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

这个虽然联通，但是实际上不能这么切块，写完整的话如下

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

B块和中间连不上，所以实际上我还得要求第一行和第一列至少要出现01各1次

 

从左到右，从上往下标记行列的话

对于n*n的矩阵M，如果M[1, n] = 0，如果存在其他的0，则必然M[1, n-1]为0（否则无法连通）

如果M[1, n-1] = 0，如果M[1, n-2] != 0，且存在0在前n-3列，则M[2, n-1] = M[2, n-2] = 0 （否则无法连通）

感觉这边似乎也可以考虑递推一下，我再仔细思考一下

 

  

7 小时前, Muriya Tensei 说道:

大佬来了，大佬分析还是准的，就差一点小细节了

不是大佬，我差的这点小细节实际上很头疼……

一月 10, 2021，由yhz012修改

[yhz012]

11 小时前, Muriya Tensei 说道:

如果1代表右侧部分，0代表左侧的话，应该是0如果出现则左下必然是0，不然对称产生的0不连通 或 导致1不连通

想了一下，好像可以沿着这个思路搞

 

考虑第一行

引理1：第一行的01必然只会翻转一次。即存在0 <= x <= n，使得M[1, :x] = 0, M[1, x:] = 1。否则会出现0被1包住的不连通情况。（备注：行列对称所以第一列同理）

 

想了下，可以直接把第一行第一列展平，展平后的依然只能有且仅有一次翻转

 

然后似乎就可以丢掉第一行第一列开始递推一下了

一月 11, 2021，由yhz012修改