正方形瓷砖合并算法

Question

正方形瓷砖合并算法

3

我有一个8x8的正方形棋盘，上面可以放置不同颜色的方形瓷砖。这些方形瓷砖可以是不同大小的正方形，边长范围为1到8，由于棋盘大小限制，8是最大值。

我需要找到一种算法，可以将相同颜色的正方形区域替换为与该区域本身大小相同的正方形瓷砖。

请看下面的例子：

在这些例子中，我们将标记为“x”的瓷砖颜色更改为黄色，以获得更大的黄色正方形区域。我正在寻找一种算法，可以用与该区域本身大小相同的相应瓷砖（步骤C）替换大的黄色正方形区域。也许该算法可以从我们更改颜色的瓷砖（标记为“x”的瓷砖）开始检查相邻的瓷砖。

- Francesco

这让我想起了八叉树数据结构。 - user395760

1

如果瓷砖X是两个单色正方形的角交叉点，会怎样？ - David Eisenstat

@DavidEisenstat 好问题，我猜哪个簇的方块将会“合并”可以随机确定，或者根据簇的总大小来决定（即，较大的簇将合并为一个方块）。 - Francesco

1

如果制作新的瓷砖需要再分割另一个瓷砖呢？ - David Eisenstat

1

你需要这个运行多快？暴力算法应该非常快，因为棋盘上只有9817/6=204个可能的正方形，其中许多你甚至不需要考虑，因为它们不包含你已经改变颜色的正方形；而且这204个正方形中每个正方形只包含64个或更少的1x1正方形，你只需要检查它们的颜色；这基本上给出了一个非常小的乘数，乘以204*64作为你需要用暴力算法进行的操作数量的上限，即使你需要每秒执行成千上万次这样的移动，也是微不足道的。 - user2566092

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

考虑到板子很小，也许我们可以采用暴力方法。按照大小降序迭代可能的方块，就像这样。

for (int width = 8; width > 0; width--) {
    for (int x0 = 0; x0 <= 8 - width; x0++) {
        for (int y0 = 0; y0 <= 8 - width; y0++) {
            int x1 = x0 + width;
            int y1 = y0 + width;
            ...
        }
    }
}

对于每个现有的正方形S，测试候选正方形 [x0, x1] * [y0, y1] 是否与S相交，如果是，则检查它是否包含S。如果S相交但不被包含，则 [x0, x1] * [y0, y1] 不是一个可能的替换。如果S被包含但颜色不正确，则同样如此。

如果候选者通过了这些测试（并且包含更改后的正方形，以防原始棋盘比应有的更多），则将其放置，并删除其中包含的正方形。