.net - 在有障碍物的给定空间中获取矩形的最大可能范围
问题描述
我正在处理以下问题:
有一个带有空单元格的网格(空单元格以白色显示)。此网格中的各个单元格已经被元素“占据”(元素以橙色显示)。
现在我有了一个矩形的起点(在本例中为第 6 行,第 3 列)。这个矩形应该占据尽可能多的空闲单元格。矩形应在橙色元素处或网格结束时停止。
随附的屏幕截图显示了 2 个网格场景及其解决方案。
左边的场景将返回
width = 2
height = 5
正确的情况会回来
width = 1
height = 5
我已经尝试了很多次来编写一个简单的代码来返回该矩形的最大宽度和高度,但最后我总是得到一个又长又丑的代码。
是否有一个干净、简短的数学解决方案,或者这个简单的问题并不像一开始看起来那么简单?
解决方案
用 0-1 矩阵表示网格,其中 a1
对应于障碍物。
如果网格是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
推荐阅读
- ios - 在 xCode 9.4 和 iOS 11 中每次调用 ViewDidLoad() 方法
- python - 将结果分配给虚拟变量 _
- javascript - Node.js:具有 Promises 和异步函数管理器的线程工作者
- linux - 为什么我的 bash 脚本中不断出现“cp: cannot stat '': No such file or directory”或“cp: missing opereand”
- node.js - 通过纱线在 Docker 中运行节点应用程序
- angular - RsJX 'Map' 运算符在 Angular 6 中不起作用
- javascript - 使用 Apollo 客户端 GraphQL 时如何在父组件中获取 React Js 子组件引用
- c++ - 如何解决从向量中擦除元素的错误?
- c - R 的 isoreg 函数比唯一拟合值产生更多的结
- python - 从 href 链接中提取 CSS