1

好的，所以我必须在填充了一些点的网格中找到最大的“自由方块”，例如，有这个网格：

###---
###---
###---
---### 
---### 
---###

其中“-”是一个填充点，“#”是一个自由区。这是通过填充嵌套列表来完成的： [[###---],[###---],...,[---###]] 内部列表是网格。所以这个网格可以以任何方式填充，我应该找到一种方法来“计算”仍然可以填充的最大可能的正方形。在上面的示例中，输出将是： 9。我将再举一个例子来说明问题：

########## 
#####----# 
##--#----# 
##--#----# 
##--#----# 
##--#----# 
#####----# 
########## 
-####----# 
##########

这里的输出应该是 16，这是从 (1,6) 到 (4,9) 的平方（从 0 开始计数）

我希望有人可以帮助我解决这个问题，在此先感谢！:)

4

2 回答 2

1

这是一个相当经典的问题，在Dobb 博士的日记中得到了很好的解决。您可用的方格只是文章中的真实值方格。

于 2013-05-11T22:00:13.330 回答
1

在这种特殊情况下（仅限于您描述的正方形），您可以这样做。

首先，考虑一个只有一个字符的“正方形”：要么-要么#。看到正方形的大小只是测试一个字符是否“被接受”是微不足道的。

现在考虑一个 4x4 正方形：

--
--

或者

[['-','-'],
 ['-','-']]

你如何计算最大尺寸？你取一个元素，比如左上角，并测试它和它的三个邻居是否被取走：

>>> sq=   [['-','-'],
...     ['-','-']]
>>> sq
[['-', '-'], ['-', '-']]
>>> if(all(sq[i][j]=='-' for i in (0,1) for j in (0,1))): print 4
... 
4

所以一般来说，取一个正方形，看看它的邻居。您可以在与目标形状相同的矩阵中保持运行计数：

st='''\
########## 
#####----# 
##--#----# 
##--#----# 
##--#----# 
##--#----# 
#####----# 
########## 
-####----# 
########## '''

def max_size(mat, taken):
    """Find the largest X or a square not taken in the matrix `mat`."""
    nrows, ncols = len(mat), len(mat[0]) 
    assert nrows==ncols 
    dirs=(0,1),(1,0),(1,1) # right, down, right and down
    counts = [[0]*ncols for _ in range(nrows)]
    for i in reversed(range(nrows)):     # for each row
        assert len(mat[i]) == ncols      # matrix must be rectangular
        for j in reversed(range(ncols)): # for each element in the row
            if mat[i][j] != taken:
                if i < (nrows - 1) and j < (ncols - 1):
                    add=1+min(counts[i+x][j+y] for x,y in (dirs))
                else:
                    add=1      # edges 
                counts[i][j]=add        

    for line in counts: print(line)                               
    return max(c for rows in counts for c in rows)   # max X (or Y) number elements

table=[[c for c in s.strip()] for s in st.splitlines()]     

print (max_size(table,'#')**2)

请注意，此函数从右下角开始，向后工作到左上角，并保持可能在顶点处的最大平方的运行总和：

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 4, 3, 2, 1, 0]
[0, 0, 2, 1, 0, 4, 3, 2, 1, 0]
[0, 0, 2, 1, 0, 4, 3, 2, 1, 0]
[0, 0, 2, 1, 0, 3, 3, 2, 1, 0]
[0, 0, 1, 1, 0, 2, 2, 2, 1, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 1, 1, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

然后将结果平方为 16 (4x4) 的答案。您可以看到，计算每个正方形适合该矩阵的位置是微不足道的。每一个都是计算出来的counts，你只需将一个元组添加(i,j)到矩阵counts或另一个矩阵中。

于 2013-05-13T18:13:28.843 回答