algorithm - 检查是否可以从一组 block 构建二维形状

Question

我正在寻找一种算法或程序的通用方法来验证是否可以从一组 block 构建特定形状。

对于像下面示例中的一组单行 block ，可以将我们需要的形状转换为一条长线，并编写一个递归函数来根据 block 的长度选择 block 。

但是，使用包含多行 block 的集合(例如下例中的 2x2 正方形)来解决此任务(检查构建形状的可能性)的一般方法是什么？

Answer 1

递归解决这个问题的一种方法是从初始的黑白单元格开始，反复确定一个特定的黑色网格单元，并尝试用所有可能的部分覆盖(或“蚕食”)该网格单元方法。例如:始终选择最底部、最右侧的黑色网格单元——即，在当前子问题的所有最底部黑色单元中，选择最右侧。

某些(在实践中，大多数)覆盖所选单元格的棋子放置可以立即被识别为无效，因为它们也覆盖了一些白色单元格 - 我们知道所有白色单元格必须保持白色。如果没有任何可用 block 的“好”放置(如果它覆盖了选定的单元格并且没有白色单元格，则放置是“好”的)那么我们可以为这个子问题返回 NO:这是不可能解决的。 OTOH 如果至少有一个可用 block 的“好”放置，它可能会或可能不会导致解决方案:为了处理这个问题，每个这样的“好”放置都会产生一个子问题，其中与该放置 block 对应的黑色单元格具有被删除(即变成白色)，并且刚刚放置的棋子类型的可用棋子数量减少了一个。当没有留下任何黑色单元格时，会出现基本情况:在这种情况下我们可以返回 YES，因为我们知道可以放置棋子以获得空网格(具体来说，这涉及根本不放置任何棋子)。

这种递归方法可能会多次重新审视某些子问题。例如，如果原始网格的一部分包含一个 4x2 的黑色单元格 block ，并且您至少有以下 2 单元格 block 可用:

XX  2         Y  2
              Y

然后你可以通过以下方式填充那个 4x2 block

XXYY       YXXY       YYXX
XXYY       YXXY       YYXX

所以由此产生的子问题(缺少这个 4x2 block 并且每种类型的 block 少 2 个)将被解决 3 次不同的时间。为避免这种情况，在某些(相当严格的)情况下，您可以使用自上而下的动态编程(也称为内存)。这具有最多解决每个子问题一次的效果，但是(可能)需要存储所有可能子问题的答案(每个一位，表示是或否)，其中有 2^(m *n)*(k_1+1)*(k_2+1)*...*(k_t+1)，其中 m 和 n 是网格的宽度和高度，k_1, ..., k_t 是网格的数量不同类型作品的可用副本。在实践中，这意味着大于 5*5 的问题将无法解决(至少如果您使用网格的“明显”编码，其中每个单元格成为整数中的一个位；可能会想出一种仅需要 2^b 位的更经济的编码，其中 b 是最初为黑色 单元格的总数，而不是总体单元格的总数)。 (OTOH，如果你准备假装每种类型的作品有无限数量，你只需要存储 2^(m*n) 个答案，因为我们不需要跟踪每个作品有多少piece remain. 这可能对快速检查很有用:如果问题不能用无限数量的每种类型的 piece 解决，那么它肯定不能用有限的数量来解决。)