每个单元格要么是水'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"之前的应力之和，并将它们添加到k1中。类似地，k2是"W"之后所有树的总和。
注意：也可以使用递归！
这本质上是一个伪装的经典洪泛填充算法。对于你看到的每棵树，你都可以进行洪水填充，找到同一森林中的所有树木，然后你只需要返回你找到的最大树木数量。
进行洪水填充的一种方法是广度优先搜索。这里有一些简单的伪代码；我将把翻译作为练习，因为这是一个面试练习问题。
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
另一种方法是使用深度优先搜索。这里有一些伪代码：
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
要将其转化为工作代码，您需要解决一系列问题。您将如何跟踪访问过哪些地点？你将如何在相邻的树上迭代？
更抽象地说，这个问题相当于找到图的最大连通分量的大小，该图是由每棵树有一个节点形成的，当树彼此相邻时，树之间有边。我在这里给出的BFS和DFS伪代码是一般的BFS算法和DFS算法，只是专门用于这种特殊情况。
这两种算法——BFS和DFS——非常适合了解你是否在面试。它们总是在练习中出现，一旦你知道如何使用它们，它们就会成为真正的主力。(我记不清我需要编码多少次了！(
这很容易在例如python中实现，使用简单的呼吸优先洪泛填充算法。重点是，你需要回溯以确保正确搜索森林。试试这个
ex0="""
5
TTTWW
TWWTT
TWWTT
TWTTT
WWTTT
"""
def parse(data):
"""Returns the fields as a set of coordniates"""
lines = iter(data.splitlines())
next(lines) # skip the size
field = set()
for y, line in enumerate(lines):
for x, cell in enumerate(line):
if cell == 'T':
field.add((x, y))
return field
DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def neighbors(p):
x, y = p
for dx, dy in DIRECTIONS:
yield x + dx, y + dy
def find_forests(field):
unvisited = set(field) # copy the field
while unvisited:
first = unvisited.pop() # take any tree
queue = [first]
forest = set()
while queue:
p = queue.pop(0)
if p in unvisited:
unvisited.remove(p)
forest.add(p)
for n in neighbors(p):
if n in unvisited:
queue.append(n)
yield forest
forests = find_forests(parse(ex0))
print(max(map(len, forests))) # find largest forest
解决方案：
from collections import deque
n = int(input())
a = []
for i in range(n):
a.append(input())
used = [[False for i in range(n)] for j in range(n)]
ans = 0
for i in range(n):
for j in range(n):
if used[i][j] or a[i][j] == 'W':
continue
q = deque()
q.append((i, j))
used[i][j] = True
cnt = 0
while q:
(x, y) = q.pop()
cnt += 1
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
x_ = x + dx
y_ = y + dy
if x_ >= 0 and x_ < n and y_ >= 0 and y_ < n:
if not used[x_][y_] and a[x_][y_] == 'T':
q.append((x_, y_))
used[x_][y_] = True
ans = max(ans, cnt)
print(ans)
说明：
used-NxN数组，其中True表示已经访问了小区。我们检查所有的细胞。如果我们找到了T，并且在开始计数林(cnt(之前它没有被访问。为此，我们检查右侧、左侧、顶部和底部单元格。如果它们包含未访问的T，则我们将其添加到林中。这是BFS算法。
考虑迭代或递归方法来"探索"；森林——从一棵树开始，找到所有相邻的树，然后找到这些树的相邻树。然后找到一种方法，标记已经访问过的树，并在迭代矩阵时跳过它们。
由于没有人提到它，这里有一个标签方案的尝试，它在矩阵的每一行上顺序迭代，并使用两行和一个标签字典作为额外的空间：
def f(m):
n = len(m)
# Stores final label and size
# for each component
labels = {}
row1 = [0] * n
row2 = [0] * n
label = 0
for i in range(n):
for j in range(n):
if m[i][j] == "T":
if j == 0 or not row2[j-1]:
# No label above or to the left
if i == 0 or not row1[j]:
label += 1
labels[label] = {"size": 1, "label": label}
row2[j] = label
print("i, j: %s, %s; new label %s" % (i, j, label))
# Label only above
else:
row2[j] = row1[j]
labels[row1[j]]["size"] += 1
print("i, j: %s, %s; continuing above label %s" % (i, j, labels[row1[j]]["label"]))
# Label only to the left
elif not row1[j]:
row2[j] = row2[j-1]
labels[row2[j-1]]["size"] += 1
print("i, j: %s, %s; continuing left label %s" % (i, j, labels[row2[j-1]]["label"]))
# Labels above and to the left
else:
row2[j] = row1[j]
labels[row1[j]]["size"] += 1
print("i, j: %s, %s; continuing above label %s" % (i, j, labels[row1[j]]["label"]))
# Unequal labels above and to the left,
# relabel
if labels[row1[j]]["label"] != labels[row2[j-1]]["label"]:
print("i, j: %s, %s; relabeling %s to %s" % (i, j, labels[row2[j-1]]["label"], labels[row1[j]]["label"]))
labels[row2[j-1]]["label"] = labels[row1[j]]["label"]
row1 = row2
row2 = [0] * n
to_del = set()
for idx, lbl in enumerate(row1):
if lbl and labels[lbl]["label"] != lbl:
to_del.add(lbl)
row1[idx] = labels[lbl]["label"]
for lbl in to_del:
target = labels[lbl]["label"]
print("i: %s; combining label %s with label %s" % (i, lbl, target))
labels[target]["size"] += labels[lbl]["size"]
del labels[lbl]
return labels
import sys
data = sys.stdin.readlines()
print(f(data))
stdin:
TTTWW
TWWTT
TWWTT
TWTTT
WWTTT
标准输出：
i, j: 0, 0; new label 1
i, j: 0, 1; continuing left label 1
i, j: 0, 2; continuing left label 1
i, j: 1, 0; continuing above label 1
i, j: 1, 3; new label 2
i, j: 1, 4; continuing left label 2
i, j: 2, 0; continuing above label 1
i, j: 2, 3; continuing above label 2
i, j: 2, 4; continuing above label 2
i, j: 3, 0; continuing above label 1
i, j: 3, 2; new label 3
i, j: 3, 3; continuing above label 2
i, j: 3, 3; relabeling 3 to 2
i, j: 3, 4; continuing above label 2
i: 3; combining label 3 with label 2
i, j: 4, 2; continuing above label 2
i, j: 4, 3; continuing above label 2
i, j: 4, 4; continuing above label 2
{1: {'size': 6, 'label': 1}, 2: {'size': 10, 'label': 2}}
stdin:
WTTTT
WWWWT
WTTTT
WWTWT
WTTWW
标准输出：
i, j: 0, 1; new label 1
i, j: 0, 2; continuing left label 1
i, j: 0, 3; continuing left label 1
i, j: 0, 4; continuing left label 1
i, j: 1, 4; continuing above label 1
i, j: 2, 1; new label 2
i, j: 2, 2; continuing left label 2
i, j: 2, 3; continuing left label 2
i, j: 2, 4; continuing above label 1
i, j: 2, 4; relabeling 2 to 1
i: 2; combining label 2 with label 1
i, j: 3, 2; continuing above label 1
i, j: 3, 4; continuing above label 1
i, j: 4, 1; new label 3
i, j: 4, 2; continuing above label 1
i, j: 4, 2; relabeling 3 to 1
i: 4; combining label 3 with label 1
{1: {'size': 13, 'label': 1}}