蟒蛇发现在嵌套列表中最大的自由广场 [英] python find biggest free square in nested list

问题描述

好了，我一定要找到最大的自由广场在一些景点都充满例如一格，有此网格：

Ok, so I have to find the biggest "free square" in a grid where some spots are filled, for example, there's this grid:

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

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

Where "-" is a filled spot and "#" is a free zone. This is done by filling a nested list: [[###---],[###---],...,[---###]] The inner lists are the vertical lines on the grid. So this grid could be filled in any way, and I'm supposed to find a way to 'calculate' the biggest possible square that can still be filled. In the above example, the output would be: 9. I'll give another example to make things clear:

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

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

The output here should be 16, wich is the square from (1,6) to (4,9) (counting from 0)

我希望有人能帮助我解决这个问题，先谢谢了！ :)

I hope someone could help me with this problem, thanks in advance! :)

推荐答案

在这种特殊情况下（仅限于广场为你描述），你可以做到这一点。

In this particular case (limited to a square as you describe) you can do this.

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

First, consider a 'square' that is only one character: either - or #. It is trivial to see that the size of the square is just testing that one character as either 'taken' or not.

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

Now consider a 4x4 square:

--
--

或

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

您是如何计算的最大尺寸是多少？你把一个元素，比如左上角，并测试它和它的三个邻居，如果他们采取或不：

How do you calculate the max size? You take one element, say the upper left, and test it and its three neighbors if they are taken or not:

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

因此​​，总的来说，拿一个正方形，并​​期待在其邻国。可以保持一个正在运行的计数中，其形状相同的目标的矩阵：

So generally, take a square and look at its neighbors. You can keep a running count in a matrix that is shaped the same as the target:

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)

请注意，这个功能开始在右下角和逆向运作，左上角和保持的运行总计最大平方，可能是在顶点的：

Note that this function starts in the lower right corner and works backwards to the upper left corner and keeps a running total of the max square that could be at the vertex:

[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）的答案。你可以看到，它会很繁琐，其中每平方米将适合在这个矩阵;每个人都被计算在计数，你想补充（I，J）的矩阵<$的元组C $ C>计数或另一个。

Then square the return for the answer of 16 (4x4). You can see that it would trivial to figure where each square would fit in this matrix; every one is calculated in counts and you would just add a tuple of (i,j) to the matrix counts or another one.

这篇关于蟒蛇发现在嵌套列表中最大的自由广场的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！