黑白迭代黑白迭代算法解析

黑白迭代黑白迭代算法解析如下：

(能看完的都不容易，能看懂的更不容易╯﹏╰)

1.穷举法，64个格子，每个格子点或者不点，共有2**64种可能，数量级为10**19，算到电脑报废也算不出一个题目。

2.分块法，将8*8网格分为4个4*4网格，分开求解。

开始分块之前需要证明：4个分块的解合并之后是否与8*8网格的解一致，也就是证明分块法的可行性！

给出一个4*4网格，在网格任何区域中点击都会唯一确定一个4*4的显示图案。

给出一个5*5网格，在网格左上角4*4区域点击，还会唯一确定一个4*4的显示图案吗？答案是否！网格的第五列会影响到第四列的图案。

拓展到8*8网格时，结论不变。仔细观察，发现在4*4的网格内点击最多可以保证3*3区域的图案不变。4个分块无法满足8*8的网格！从图中可以看出，仍有很大一部分是未知数。

一个解决办法是构造补丁，如图中黑框区域所示。

具体执行逻辑：4*4网格一共65535种点击的组合，可以产生4096种图案，也就是说，每一个4*4的图案都有16种点击生成方式；而每一个在角落的3*3网格，又能在这4096个图案中找到8个3*3区域一致的(这段结论是通过实验得出来的，没有数学证明)。

所以，以左上角阴影为例，能够保证左上角阴影为想要的图案的点击组合有8*16=128种，同理其它三个阴影各有128种。

然后打补丁，我们取左上角分块(4*4大小)的右边两列和右上角分块的左边两列组成新的4*4分块。如果这个分块能够保证点击之后中间3行2列的图案和实际图案一致，那么拼接左上角和右上角两个分块就能保证点击后的图案与实际图案前三行完全一致。

后面的拼接证明同理。

然后用Python把算法实现一下，平均6-8秒解出一个答案，轻松通关

以上就是黑白迭代黑白迭代算法解析相关内容。