蟒蛇发现在嵌套表最大的自由广场(python find biggest free square in

好了，所以我必须找到最大的“自由广场”在某些点上填写，例如电网，还有这个网格：

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

其中“ - ”是一个充满斑点和“＃”是一个自由区。这是通过填充嵌套列表来完成：[[### ---]，[### ---]，...，[--- ###]内部列表是在垂直线网格。因此，这可能格以任何方式填补，而我应该找到一种方法来“计算”最大的可能是方仍然可以充满。在上面的例子中，输出将是：9我再举个例子把事情说清楚：

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

这里的输出应为16，至极是从（1,6）的平方，以（4,9）（从0开始计数）

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

Answer 1:

这是一个非常经典的问题，这是很好的解决了道博博士的杂志。你可用广场只是在文章中真正有价值的正方形。

Answer 2:

在这种特殊情况下（仅限于你描述一个正方形），你可以做到这一点。

首先，考虑一个“广场”，这只是一个字：要么-或# 。这是微不足道的看到，广场的大小只是测试一个字符作为是“采取”与否。

现在考虑一个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（4×4）的答案的回报。你可以看到，它会很繁琐，每个广场将适合在这个矩阵; 每一个在计算counts ，你想补充的元组(i,j)的矩阵counts或另外一个。