python - 最大的森林(亚马逊面试题)

Question

每个单元格要么是水“W”，要么是树“T”。给定有关该字段的信息，打印最大森林的大小。森林的大小是其中树木的数量。为清楚起见，请参阅示例案例

输入:

第一行包含矩阵 N 的大小。 接下来的 N 行每行包含 N 个字符，'W' 或 'T'。

输出:

打印最大森林的大小。

示例输入:

5
TTTWW
TWWTT
TWWTT
TWTTT
WWTTT

预期输出:10

我的代码:

t_cases = int(input())
k1 = 0
k2 = 0
for _ in range(t_cases):
    list1 = (input())
    z = 0
    list2 = []
    for i in range(len(list1)):
        z = list1.count('T')
        if list1[i] == "W":
            break
        elif list1[i] == "T":
            list2.append(list1[i])
            
    k1 = k1 + list2.count('T')
    if z > list2.count('T'):
        k2 = k2 + (z - list2.count('T'))
    else: 
        k2 = k2 + (list2.count('T')- z)
if k1 > k2:
    print(k1)
else: 
    print(k2)

我的代码满足示例输入但未能通过每个测试用例。此代码计算所有情况下“W”之前的 tress 之和，并将它们添加到 k1。同样，k2是'W'之后所有树的总和。

注意:也可以使用递归!

Answer 1

这本质上是经典flood-fill algorithm伪装。对于您看到的每棵树，您都可以运行泛洪填充以查找同一森林中的所有树，然后您只需从那里返回找到的最大树数。

一种进行泛洪填充的方法是使用 breadth-first search .这是一些简单的伪代码；我将把翻译留作练习，因为这是一道面试练习题。

max_forest = 0
for each location:
    if it's a tree, and you haven't visited it yet:
        max_forest = max(max_forest, size_of_forest(location))
return max_forest

size_of_forest(location):
    if this location has been visited already, return 0
    make a worklist of locations, initially just the start.
    
    size = 1
    while the worklist isn't empty:
        remove one element from the worklist.
        increment size.

        for each neighboring tree:
            if that location isn't yet visited:
                mark that location visited.
                increment size.
                add the location to the worklist.

        return size

另一种方法是使用 depth-first search .这是一些伪代码:

size_of_forest(location):
    if this location is visited, return 0
    mark this location as visited

    result = 0
    for each neighboring tree:
        result += size_of_forest(that tree)

    return result

要将其转化为工作代码，您需要解决大量问题。您将如何跟踪访问过哪些位置？您将如何遍历相邻的树？

更抽象一点，这个问题相当于求最大的connected component的大小通过每棵树有一个节点而形成的图，当它们彼此相邻时树之间有边。我在这里给出的 BFS 和 DFS 伪代码是通用的 BFS 和 DFS 算法，专门针对这种特殊情况。

这两种算法 - BFS 和 DFS - 非常适合您在外出面试时了解。它们在实践中一直出现，一旦您知道如何使用它们，它们就是真正的主力军。 (我已经记不清我需要编写这些代码多少次了!)