在大图中搜索简单图

Question

我创建了大图由正方形组成。 另外我也有一些简单数字也包括正方形。

如何才能找到我的简单数字中的大图？

- 谢谢。

Answer 1

既然你说的方块位于一个网格上，你可以尝试简单地在每个小图形上循环网格，看看相应的方块是否相等。如果是这样，你已经找到了一个简单数字的例子。

如果您想要更有趣，可以将简单数字编码为不相交的路径，即第一个简单图形可能是如下路径：从开始，向右移动。然后，对于大数字的每个方块，如果您可以完成路径并留在大数字的方块上，那么您已经找到了一个单个数字的实例。

Answer 2

假设大数字B的每一行都是由一系列比特组成的，假设最大的小数字可以包含在h-by-v网格中。 （在你的例子中，h = 3，v = 2）。使用h * v位（或者更多的例如4 * 2或4 * 4或8 * 2等等）为每个小图形做一个掩模M_s。在每个（x，y）处向下和向下移动一个h-by-v“窗口”，形成值M（x，y），该值表示在B中设置的位于当前窗口中的位。 （这个值可以递增计算，即通过移动窗口的每一行一位进入。）每当M_s & M(x,y) == M_s，你已经发现了一个小数字s的发生。

注意，上述方法假设，在一个小的数字空白细胞是“无关”，即可以匹配在B.空白或非空白如果这种细胞不“不要不关心“，那么除了以前使用的非空白图之外，每个小图还需要一张空白补充图。该映射针对M（x，y）的补码进行测试。如果M（x，y）窗口的大小与小图相同，则可以将测试组合在一起并测试M_s^M(x,y) == 0而不是M_s & M(x,y) == M_s。如果B非常大并且稀疏，那么移动小图形模式并直接对B的单词进行测试可能会更快，而不是将B的比特变成M（x，y）的值;或预先计算移位的小图案阵列。

如果小数字的数量很大，请对它们进行排序，使得如果w中包含小数字u，则只要找不到u，就可以跳过对w的测试。同样，如果u和v都包含在w中，则只要找不到u或v中的任何一个，就可以跳过对w的测试。但是，如果第一段中概述的基本方法太慢，则应该只尝试像这样和以前的优化。