algorithm - 固定大小的正方形包装在有障碍物的网格上

我正在寻找一种算法，它可以在有障碍物的网格中找到所有给定大小的非重叠正方形所有正方形必须具有相同的大小，这将作为输入之一给出。
带有代表空白区域的黑色单元格和代表障碍物的红色单元格的示例网格。接下来是一个在网格中找到多个5x5黄色正方形的示例解决方案：


到目前为止，我所拥有的是一个算法，它使用动态规划来找到最大平方，但我不知道它是否对上述问题有用也许可以修改它来找到多个正方形。

var width = 10, height = 10;
var grid = new Array(width * height);
var sizes = new Array(width * height);

function findBiggestSquare() {
    var bestSize = -1, bestLocation = -1;

    for (var i = grid.length - 1; i >= 0; i--) {
        var size = 0;

        if (grid[i] === 0) {
            size = 1 + Math.min(sizes[i+1], sizes[i+width], sizes[i+1+width]);

            if (size > bestSize) {
                bestSize = size;
                bestLocation = i;
            }
        }

        sizes[i] = size;
    }

    if (bestLocation !== -1)
        return {'size': bestSize, 'location': bestLocation};
    else
        return null;
}

最佳答案

通过检查网格每个NxN部分中的障碍物，可以轻松找到这些正方形的所有潜在中心可以进行一些简单的优化下面是用橙色表示潜在中心的示例：

虽然拾取中心单元更容易可视化，但您可能需要使用角点这样，就不必担心N的奇偶性，剩下的可能更简单。
一旦有了这些突出显示的单元格，请为每个单元格分配一个数字，该数字等于如果在其中放置一个正方形，则无法使用的其他突出显示单元格的数量例如，如果有潜在左上角的列表，则分配给其中一个的数字是以其为中心的2*N-1正方形中潜在左上角的数目。
然后，选择要放置正方形的最小数字的单元格，并相应地更新网格重复以上步骤，直到列表为空。

关于algorithm - 固定大小的正方形包装在有障碍物的网格上，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53480163/