将一定尺寸的矩形放入矩阵自由区域的算法
Algorithm for placing rectangle with certain size into free area in matrix
问题
我需要将大小为 n×m 的矩形放置到大小为 N×M 的矩阵的自由区域中，其中 N=n*2-1，M=m*2-1。如果矩阵单元格为 true，则认为它是空闲的，如果它是 false，则认为它已被占用。中心单元格始终是 true，并且由于矩形和矩阵的大小，始终位于矩形内。
附加要求是矩形左上角和中心单元格之间的距离必须尽可能小。
n=8 和 m=5 的示例：
其中灰色单元格 - 已占用，绿色 - 中心单元格，蓝色单元格 - 解决方案矩形，红线 - 矩形左上角与中心单元格之间的距离。
尝试次数
蛮力解决方案的时间复杂度为 O(N×M×n×m)，这不是最优的。如果我预处理矩阵，我可以消除某些单元格中的计算，但这仍然会花费太多时间。
最初我认为我可以采用最大矩形问题并将条件从最大修改为需要，但它进入了死胡同（我需要在直方图中列出所有矩形，我不知道如何做到）。然后我认为这就像打包问题，但我能找到的只是最初完全为空 space 和多个矩形的版本，不适用于此问题。
上下文
过去，当用户单击网格时，我的程序会放置矩形，如果它是空的，则左上角与单击点重合，如果它占据了矩形放置的单元格，则会失败。我决定修改此行为，而不是失败，为矩形找到最合适的位置，同时仍然包含一个点击点。上图矩阵中，点击点为绿色单元格，矩阵大小代表矩形的所有可能位置。
P.S。如果可能的话，我更喜欢真实的语言示例而不是 pseudo-code。我的程序是用Java写的，但任何语言都可以。
您可以在 O(N.M) space 中执行此操作，时间复杂度为：
- 计算
O(N.M) 中的 summed area table
- 遍历所有左上角，检查矩形中总面积是否等于
n.m，如果到中心的距离有所改善，则更新最佳位置。测试是每个左上角 O(1) 个，左上角有 O(N.M) 个，所以整体 O(N.M)
关键思想是总面积 table 允许您在 O(1) 时间内计算任意矩形的总和。
问题
我需要将大小为 n×m 的矩形放置到大小为 N×M 的矩阵的自由区域中，其中 N=n*2-1，M=m*2-1。如果矩阵单元格为 true，则认为它是空闲的，如果它是 false，则认为它已被占用。中心单元格始终是 true，并且由于矩形和矩阵的大小，始终位于矩形内。
附加要求是矩形左上角和中心单元格之间的距离必须尽可能小。
n=8 和 m=5 的示例：
其中灰色单元格 - 已占用，绿色 - 中心单元格，蓝色单元格 - 解决方案矩形，红线 - 矩形左上角与中心单元格之间的距离。
尝试次数
蛮力解决方案的时间复杂度为 O(N×M×n×m)，这不是最优的。如果我预处理矩阵，我可以消除某些单元格中的计算，但这仍然会花费太多时间。
最初我认为我可以采用最大矩形问题并将条件从最大修改为需要，但它进入了死胡同（我需要在直方图中列出所有矩形，我不知道如何做到）。然后我认为这就像打包问题，但我能找到的只是最初完全为空 space 和多个矩形的版本，不适用于此问题。
上下文
过去，当用户单击网格时，我的程序会放置矩形，如果它是空的，则左上角与单击点重合，如果它占据了矩形放置的单元格，则会失败。我决定修改此行为，而不是失败，为矩形找到最合适的位置，同时仍然包含一个点击点。上图矩阵中，点击点为绿色单元格，矩阵大小代表矩形的所有可能位置。
P.S。如果可能的话，我更喜欢真实的语言示例而不是 pseudo-code。我的程序是用Java写的，但任何语言都可以。
您可以在 O(N.M) space 中执行此操作，时间复杂度为：
- 计算
O(N.M) 中的 summed area table
- 遍历所有左上角，检查矩形中总面积是否等于
n.m，如果到中心的距离有所改善，则更新最佳位置。测试是每个左上角O(1)个，左上角有O(N.M)个，所以整体O(N.M)
关键思想是总面积 table 允许您在 O(1) 时间内计算任意矩形的总和。