我正在处理以下问题:
有一个带有空单元格的网格(空单元格显示为白色)。该网格中的各个单元格已经被元素“占据”(元素以橙色显示)。
现在我有了一个矩形的起点(在本例中为第 6 行,第 3 列)。该矩形应占据尽可能多的空闲单元。矩形应在橙色元素处或网格结束时停止。
所附屏幕截图显示了 2 个网格场景及其解决方案。
左边的场景将会返回
width = 2
height = 5
正确的场景将会回归
width = 1
height = 5
我曾多次尝试编写一个简单、简单的代码来返回该矩形的最大宽度和高度,但最终我总是得到一个又长又难看的代码。
是否有一个干净、简短的数学解决方案,或者这个简单的问题并不像最初看起来那么容易?
最佳答案
用 0-1 矩阵表示网格,其中 1
对应于障碍物。
如果网格为 m x n
且 (a,b)
是起始单元格从 0 开始的行索引和列索引,则 width = n-b
表示从该单元格开始的矩形的最大可能宽度,而不考虑任何障碍物。这是当前的宽度。现在,开始从该单元格向下扫描列,直到遇到底部边缘或障碍物。对于该列中的每个单元格,开始向右扫描,直到遇到障碍物或达到当前宽度。如果首先遇到障碍物,请减小当前宽度。将当前宽度追加到宽度列表中(无论当前宽度是否已减小)。
在此阶段,您将获得一个宽度列表,其中每个潜在高度对应一个宽度。只需扫描此列表,将每个宽度乘以相应的高度(即 1 + 基于 0 的列表索引)。返回最大化产品高度*宽度的对(高度,宽度)。
Python 实现:
def find_max_rect(grid,a,b):
if grid[a][b] == 1: return (0,0)
m = len(grid) #number of rows
n = len(grid[0]) #number of columns
width = n-b #maximum possible width given starting column
widths = []
i = a
while i < m and grid[i][b] == 0:
#scan right from (i,b+1) until a 1 or current width is hit
for j in range(b+1,b+width):
if grid[i][j] == 1:
#an obstacle forces width to contract
width = j-b #number of steps before obstacle
break #out of inner loop
widths.append(width)
i += 1
max_area = 0
max_at = -1
for i,width in enumerate(widths):
if (i+1)*width > max_area:
max_area = (i+1)*width
max_at = i
return (max_at + 1,widths[max_at])
测试如下:
test_grid = [[1,0,1,1,0],
[0,1,0,0,0],
[0,1,0,0,0],
[0,1,0,0,0],
[0,0,0,1,0],
[0,0,0,1,0],
[0,0,0,0,1],
[0,0,0,0,0],
[1,0,0,0,0],
[0,0,0,0,1],
[0,1,0,0,0]]
print(find_max_rect(test_grid,6,2)) #prints (5,2)
编辑时:我意识到没有理由只存储候选宽度以迭代它们一次。相反,您可以动态跟踪最佳区域。以下代码在功能上等效但更高效:
def find_max_rect(grid,a,b):
if grid[a][b] == 1: return (0,0)
m = len(grid) #number of rows
n = len(grid[0]) #number of columns
current_height = 0
current_width = n - b #maximum possible width given starting column
max_area = 0
best_height, best_width = current_height, current_width
i = a
while i < m and grid[i][b] == 0:
current_height += 1
#scan right from (i,b + 1) until a 1 or current width is hit
for j in range(b + 1,b + current_width):
if grid[i][j] == 1:
#an obstacle forces width to contract
current_width = j - b #number of steps before obstacle
break
#decide if the best should be adjusted
current_area = current_height * current_width
if current_area > max_area:
best_area, best_height, best_width = current_area, current_height, current_width
i+=1
return best_height, best_width
关于.net - 获取给定空间内有障碍物的矩形的最大可能范围,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52375702/