.net - 获取给定空间内有障碍物的矩形的最大可能范围

Question

我正在处理以下问题:

有一个带有空单元格的网格(空单元格显示为白色)。该网格中的各个单元格已经被元素“占据”(元素以橙色显示)。

现在我有了一个矩形的起点(在本例中为第 6 行，第 3 列)。该矩形应占据尽可能多的空闲单元。矩形应在橙色元素处或网格结束时停止。

所附屏幕截图显示了 2 个网格场景及其解决方案。

左边的场景将会返回

width = 2
height = 5

正确的场景将会回归

width = 1
height = 5

我曾多次尝试编写一个简单、简单的代码来返回该矩形的最大宽度和高度，但最终我总是得到一个又长又难看的代码。

是否有一个干净、简短的数学解决方案，或者这个简单的问题并不像最初看起来那么容易？

谢谢。 .

Answer 1

用 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