Python网格搜索

Question

我有一个网格，定义如下：

['..##.......', 
 '#...#...#..', 
 '.#..#.#..#.', 
 '..#.#...#.#', 
 '.#...##..#.', 
 '..#.##.....', 
 '.#.#.#....#',
 '.#..#.....#',
 '#.###..#...', 
 '#....#....#',
 '.#......#.#']

[2, 7, 3, 3, 8, 2, 3, 3, 4, 7, 3, 2, 3, 12, 2, 4, 3, 5, 3, 3, 4, 4, 7]

其中，点是一个空空间，#是满的。现在我需要做的是通过搜索网格来找到最大的矩形。在这个例子中，它是12 (6-8，所有行都包含4个点)。我所做的就是保存第一个坐标，穿过x，看看空格是否是空的。如果它是空的，我保存x直到我发现它是满的。如果是满的，我去检查相同长度的下面一行，并继续它，直到我找到一排，如果不是完全空的。

如果y>0，我也检查上面，这样就可以得到重叠的。我的问题是，我的程序在这个数组上运行得很好，这两个也是：

['..##.......', 
 '#...#...#..', 
 '.#..#.#..#.',
 '..#.#...#.#', 
 '.#...##..#.',
 '..#.##.....']

最大为7，给出数组= 2，7，3，3，6，2，3，3，4，5，3，2，3，3，3，3，3，3，3，3，3，3，3

['..##.......', 
 '#...#...#..', 
 '.#..#.#..#.', 
 '..#.#...#.#', 
 '.#...##..#.', 
 '..#.##.....']

最大是8，给出一个数组= 8，7，7，2，4

但如果我尝试这样的方法：

['.#.#.', 
 '...#.',
 '...#.',
 '####.',
 '#....',
 '#...#']

它返回8而不是6，并给出一个数组=8、7、7、2、4、3。问题是什么？

这是我的密码

gen = ((x, y) for y in range(0, len(array)) for x in range(0, len(array[0])))
loc = {"x1": 0, "y1": 0, "x2": 0, "y2": 0}
temp = []
count = 0
for x, y in gen:
    if not array[y][x] == "#":
        loc["x2"] = x
        count += 1
    elif count > 1:
        i = 0
        check = False
        temp_y = y
        y += 1
        while i <= loc["x2"] and y < len(array):
            if not array[y][i] == "#":
                if i == loc["x2"]:
                    check = True
            else:
                break
            if check:
                count += i + 1
                i = 0
                loc["y2"] = y
                y += 1
                check = False
            else:
                i += 1
        y = temp_y
        if y > 0:
            i = 0
            y -= 1
            while i <= loc["x2"] and y < len(array):
                if not array[y][i] == "#":
                    if i == loc["x2"]:
                        check = True
                else:
                    break
                if check:
                    count += i + 1
                    i = 0
                    loc["y2"] = y
                    y -= 1
                    check = False
                else:
                    i += 1
        temp.append(count)
        count = 0
        loc["x1"] = x
        loc["y1"] = y
print(temp)
print(max(temp))

所以我要做的是，找到一个空的空间，然后检查下面和上面的高度。我还在计算它有多大(从它合并的空位数)，然后在另一个数组(带有数字的数组)中保存这个数量。

示例：

['...#..']
['3, 2]

或者更大的：

['...#...#.#',
 '....#.###.',
 '###...####']
[6 (because of the second row), 3, 1, 4, 5, 1, 1, 3]

问题是(见下文)，它工作正常，直到到达第三行，然后它就会失去理智。

['..##.......', 
 '#...#...#..', 
 '.#..#.#..#.', 
 '..#.#...#.#', 
 '.#...##..#.', 
 '..#.##.....', 
 '.#.#.#....#',
 '.#..#.....#',
 '#.###..#...', 
 '#....#....#',
 '.#......#.#']
 [2, 7, 3, 3, 8, 2, 3, 3, 4, 7, 3, 2, 3, 12, 2, 4, 3, 5, 3, 3, 4, 4, 7]

Answer 1

也许一种更直截了当的方法会有所帮助：

如果您首先构建一个矩阵，其中包含从每个位置直走的连续点数，那么将这些值组合起来将更容易得到面积最大的矩形的坐标。

from itertools import accumulate
def bigRect(board):
    spanSize = [ list(map(len,row.split("#"))) for row in board ]
    # print([s for ss in spanSize for s in ss if s>0]) # your array of numbers
    spans    = [ [c for s in ss for c in range(s,-1,-1)] for ss in spanSize ]
    result   = (0,0,0,0,0) # area, height, width, top, left
    for r,row in enumerate(spans):
        for c in range(len(row)):
            nextSpans = accumulate( (spanRow[c] for spanRow in spans[r:]),min)
            rectSize  = max( [(w*h,h,w) for h,w in enumerate(nextSpans,1)] )
            result    = max(result,rectSize+(r,c))
    return result

示例输出：

B0 = ['..##.......', 
      '#...#...#..', 
      '.#..#.#..#.', 
      '..#.#...#.#', 
      '.#...##..#.', 
      '..#.##.....', 
      '.#.#.#....#',
      '.#..#.....#',
      '#.###..#...', 
      '#....#....#',
      '.#......#.#']

area,height,width,top,left = bigRect(B0)
print("Area:",area,"Size:",(height,width),"Top-Left:",(top,left))

# Area: 12 Size: (3, 4) Top-Left: (5, 6)

for row in B0[top:top+height]:
    print(row[left:left+width])
    
# ....
# ....
# ....        

的工作方式：

第一步是构建spans矩阵，该矩阵将包含从每个位置直接指向的连续点数。

要计算这一点，每一行都要在“#”字符上拆分，以确定“.”的数目。在它们之间(spanSize对每一行都有拆分子字符串的长度)。

所以'.#...##..#.‘(第5行)将转换为1,3,0,2,1。每个数字代表从第一个点的位置到下一个'#’点的计数。将数字降至零将产生具有相同含义(即“”的数目)的个别头寸的值。直到下一个'#')：

(1,0),(3,2,1,0),(0),(2,1,0),(1,0) --> 1,0,3,2,1,0,0,2,1,0

对于上面的例子，spans将包含以下内容：

[2, 1, 0, 0, 7, 6, 5, 4, 3, 2, 1, 0]
[0, 3, 2, 1, 0, 3, 2, 1, 0, 2, 1, 0]
[1, 0, 2, 1, 0, 1, 0, 2, 1, 0, 1, 0]
[2, 1, 0, 1, 0, 3, 2, 1, 0, 1, 0, 0]
[1, 0, 3, 2, 1, 0, 0, 2, 1, 0, 1, 0] <-- '.#...##..#.' example
[2, 1, 0, 1, 0, 0, 5, 4, 3, 2, 1, 0]
[1, 0, 1, 0, 1, 0, 4, 3, 2, 1, 0, 0]
[1, 0, 2, 1, 0, 5, 4, 3, 2, 1, 0, 0]
[0, 1, 0, 0, 0, 2, 1, 0, 3, 2, 1, 0]
[0, 4, 3, 2, 1, 0, 4, 3, 2, 1, 0, 0]
[1, 0, 6, 5, 4, 3, 2, 1, 0, 1, 0, 0]

现在，如果您获取每个位置并分析同一列中的后续值，则可以确定该位置上的最大矩形(作为左上角)。

这是通过构建下一个值的列表来执行的，这些值沿着列向下移动，但仅保留沿途的最小跨度宽度。(这就是accumulate(...,min)所做的)。

例如，从(0,5)位置，列中的值为6、3、1、3、0、.累积我们得到的最小值: 6,3,1,1,0,0,0，.这些是高地1，2，3，4的可用宽度.我们可以使用相应的区域来选择最大的高度和宽度组合：

 Height  width   area 
   1       6      6
   2       3      6
   3       1      3
   4       1      4
   5       0      0
   6       ... all will be zero from there onward

由此我们发现左上角为(0,5)的最大矩形的面积为6，可以是1x6，也可以是2x3。

对每个位置都这样做，您可以跟踪最大的区域并返回它的大小和坐标。

Answer 2

Python索引允许您对列表中的items[-1]最后一个项执行操作。在我看来，在检查矩形的时候，它是“环绕”的，所以你可以看到矩形从左边延伸到右边。

要解决这个问题，请确保索引始终在正确的范围内(例如大于0且小于长度)。

Answer 3

在代码中查找错误并不是一项容易的任务。我发现它没有足够的可读性来审查它。相反，我决定发布代码，这做了我认为你所描述的你的算法。希望能帮上忙。如果不是，评论，忽略，或否决，如果你认为这是真正的主题。

class Grid:
    def __init__(self, grid):
        self.grid = grid
        self.xsize = len(grid)      # must be non-zero
        self.ysize = len(grid[0])

    def is_empty(self, x, y): 
        """Is this an empty cell in the grid?"""
        if not 0 <= x < self.xsize or not 0 <= y < self.ysize:
            return False
        return self.grid[x][y] == '.' 

    def count_empty(self, x, y): 
        """count adjacent empty cells in a line starting at (x,y)."""
        cnt = 0 
        while self.is_empty(x, y): 
            cnt += 1
            y += 1
        return cnt 

g = Grid(array)

for x in range(g.xsize):
    for y in range(g.ysize):
        if not g.is_empty(x, y): 
            continue
        print(f"rectangle(s) at ({x}, {y}):")
        ry = g.ysize
        for rx1 in range(g.xsize):
            ry = min(ry, g.count_empty(x + rx1, y))
            if ry == 0:
                break
            print(f"  {rx1 + 1}*{ry}")

为了简洁起见，我不计算矩形大小以找到最大值。稍后再添加这一点是微不足道的。它只会打印所有的直肠。

代码将每个空单元格视为矩形的左上角，而不仅仅是一个矩形，它还检查大小为1xN、2xN、3xN等。所有的坐标都是x，y=线，列。

输出如下所示：

rectangle(s) at (0, 0):
  1*2
rectangle(s) at (0, 1):
  1*1
  2*1
rectangle(s) at (0, 4):
  1*7
rectangle(s) at (0, 5):
  1*6
  2*3
  3*1
  4*1
... lines deleted ...
rectangle(s) at (5, 6):
  1*5
  2*4
  3*4   <--- here is what you were looking for
  4*1
  5*1
  6*1
rectangle(s) at (5, 7):
  1*4
  2*3
  3*3
... etc ...