Post #43

今年 Hackergame 中有一道题“马赛克”，我本来以为很简单，但这两天写得挺折腾的，过程如下： 首先，当然是要存储对每个二维码块的知识（已知黑/已知白/未知），并计算出每个马赛克块由哪些二维码块按多少权重构成。其次，对每个马赛克块，尝试其下未知的二维码块的所有可能性，看是否只有一种可能性算出来的颜色和实际颜色匹配，如果是则将相关二维码块记录为已知。 这个思路解出的块太少，因为每个马赛克块都覆盖 9 个二维码块，如果全部未知的话有 512 种可能性。但马赛克块的颜色只有 256 种可能性，多数情况下都不能解出。改进方案：不断迭代，用已知信息进一步求解未知信息。 迭代几步后就无法取得进展了，此时仍然有很多块没有解出。我尝试把结果画出（试了两种画图方案，1. 未解出的块画成原始马赛克的颜色 2. 将 1 的结果二值化）并扫描，发现无法成功识别。 想到几个进一步优化的思路： 1. 马赛克遮住了 4 个小牛眼，它们可能对于识别更有帮助，所以手工在程序开始前标记为已知。 2. 对于某个马赛克块下方的二维码块，即使存在多种合理的可能性，无法唯一确定整个解，但只要某个二维码块在所有这些可能性中都是同一个颜色，就可以将它单独标记为已知。 3. 当迭代无法取得进展时，找出第一个仍未解出的二维码块，猜测它分别是白色和黑色，进一步求解。求解过程中如果再次无法取得进展就递归再猜，如果发现某个马赛克块无解就返回，如果成功解出就输出并返回。 把这几个优化都实现了，发现 1 和 2 能帮助多解出一点，但还是无法识别。3 比较成问题，应该是因为很多地方理论上就是无法确定，无论猜测成什么都不会有冲突，它们的笛卡尔积非常巨大，所以程序会输出成百上千个可能的解。因此不得不再加入一个功能，直接将每个解送入一个马赛克识别程序，识别成功才输出。跑了几分钟后终于解出了。 回去读官方题解，发现官方题解并没有做这些优化。研究了一番发现问题在于： 1. 给二维码加上正确的白边有助于提高识别成功率 2. 即使是未解出的块，整个方块内部也应该显示成一个统一的颜色，否则难以识别成功。例如将未解出的块全部显示成白色或者全部显示成黑色都可以识别成功。但我在这个阶段，只尝试了将未解出的区域显示原始马赛克颜色，或者二值化的结果，这都会导致一个二维码方块内部颜色不统一（因为马赛克的边界可能发生在二维码块内部），可能影响了边界判断相关的逻辑，导致一直没有识别成功。 （怪不得解出人数这么少，比赛过程中我一直好奇来着）