在矩阵中将具有一定大小的矩形放入空闲区域的算法
问题
我需要将大小为n×m的矩形放置到大小为N×M的矩阵的空闲区域中，其中N=n*2-1 ， M=m*2-1 。 矩阵单元如果是true ，则认为是空闲的，如果它是false ，则被占用。 中心单元始终为true ，并且由于矩形和矩阵的大小，总是会在矩形内。
附加要求是矩形左上角与中心单元之间的距离必须尽可能小。
n=8和m=5示例：
灰色单元格占用，绿色中心单元格，蓝色单元格 - 矩形解决方案，红色线条 - 矩形左上角与中心单元格之间的距离。
尝试
蛮力解决方案将具有O（N×M×n×m）时间复杂度，这不是非常优化的。 如果我预处理矩阵，我可以消除某些单元格中的计算，但仍需要太多时间。
起初，我以为我可以采取最大矩形问题，只是修改条件从最大需要，但它走到了死胡同（我需要列出直方图中的所有矩形，我不知道如何）。 然后我认为它就像包装问题，但我能找到的只是最初完全空白的空间和多个矩形的版本，这不适用于这个问题。
上下文
在过去，当用户点击一个网格时，我的程序会放置一个矩形，左上角与点击点重合，如果它是空的，并且如果它占据了矩形所在的单元格，则失败。 我决定修改这个行为，而不是失败，找到矩形的最合适的位置，同时还包含点击点。 在上面的矩阵图中，点击点是一个绿色单元格，矩阵大小表示矩形的所有可能位置。
PS如果可能的话，我宁愿选择真正的语言示例而不是伪代码。 我的程序是用Java编写的，但任何语言都可以。
您可以通过以下方式在O(NM)空间和时间复杂度中执行此操作：
O(NM)的求和面积表 nm ，如果到中心的距离已经改善，则更新最佳位置。 测试是每个左上角O(1) ，并且有O(NM)左上角，所以整体O(NM) 关键的想法是，求和面积表允许您计算O（1）时间内任意矩形的总和。
链接地址: http://www.djcxy.com/p/63245.html上一篇: Algorithm for placing rectangle with certain size into free area in matrix