arrays - 通过仅检查 "open"索引的列表来查找网格中所有最大的开放矩形的列表

Question

我有一个二维网格，其中有一些障碍物。

[x][x][ ]
[ ][ ][ ]
[ ][ ][x]

我希望能够找到“开放”网格单元的所有最大空间。

[x][x][ ]       [x][x][ ]
[1][1][ ]       [2][2][2]
[1][1][x]  and  [ ][ ][x]

我看到了问题here这是相似的;但是，我可以访问的数据不是二维值数组。我有一个只有开放/可用索引的列表，它存储在一个一维数组中。使用上面的示例，我的数据如下所示:

[0,2]
[1,0]
[1,1]
[1,2]
[2,0]
[2,1]

我可以将它转换为二维数组，但我不想为此再次遍历所有项目。我觉得有一些非常简单的解决方案，但我似乎找不到。

有没有办法只通过检查开放索引列表来找到所有最大的矩形？

编辑 我只是决定将开放索引数组更改为表示整个网格的二维数组，然后使用我链接到的算法。这对我的初始测试来说足够有效；但是，我有兴趣了解其他可能的解决方案，如果我需要更改我的实现以解决性能或空间问题。

Answer 1

当然。

要找到一个矩形:

• 从任何空闲单元格开始。假设这将是左上角。
• 看能不能横向扩展。
• 看看能不能纵向延伸。
• 回溯。

稍后我会对此进行详细说明，但我认为这可以让您快速入门。