蟒蛇發現在嵌套列表

Question

好了最大的自由廣場，所以我必須找到最大的「自由廣場」在某些點上填補了網格，例如，有此網格：

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

在哪裏「 - 「是一個填補的地方，」＃「是一個自由區。 這是通過填充一個嵌套列表完成的： [[### ---]，[### ---]，...，[--- ###]] 內部列表是垂直網格上的線。 因此，這個網格可以以任何方式填充，我應該找到一種方法來「計算」仍然可以填充的最大可能的正方形。在上面的例子中，輸出將是：9 我再舉個例子把事情說清楚：

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

這裏的輸出應爲16，至極爲（1,6）的平方（ 4,9）（從0開始計數）

我希望有人能幫助我解決這個問題，提前致謝！ :)

Answer 1

這是一個相當經典的問題，很好地解決了Dr. Dobb's Journal。您可用的正方形只是文章中真實值的正方形。

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（4x4）的回答進行平方迴歸。你可以看到，找出每個正方形適合這個矩陣的位置是很微不足道的;每個人都在counts中計算，您只需將(i,j)的元組添加到矩陣counts或另一個。