给定一些由1和0组成的m乘n网格，你如何找到它会捕获多少水，其中1是"墙"，0是空白？
示例：
[1, 1, 1, 1, 1],
[1, 0, 0, 0, 1],
[1, 0, 0, 0, 1],
[1, 0, 0, 0, 1],
[1, 1, 1, 1, 1]
这个网格可以捕获9个单位的水。
[1, 1, 1, 0, 1],
[1, 0, 0, 0, 1],
[1, 0, 0, 0, 1],
[1, 0, 0, 0, 1],
[1, 1, 1, 1, 1]
然而，由于该网格的一面墙上有"泄漏"，因此将捕获0个单位的水。
[1, 1, 1, 0, 1],
[1, 0, 1, 0, 1],
[1, 0, 1, 0, 1],
[1, 0, 1, 0, 1],
[1, 1, 1, 1, 1]
同样，由于两个部分之间有一个隔板，泄漏的一个不会影响另一个，因此该格栅将捕获3个单位的水。
我真的不知道该如何着手解决这个问题。有什么算法对此有帮助吗？我在考虑深度优先搜索或某种洪水填充，但现在我不确定这些是否适用于此练习。
您可以创建一个从边上0的位置开始的泄漏列表。然后用泄漏位置旁边的0展开该列表(直到不能添加更多泄漏为止(。最后，从网格中的零总数中减去泄漏数。
def water(G):
rows = len(G)
cols = len(G[0])
# initial leaks are 0s on edges
leaks = [ (r,c) for r in range(rows) for c in range(cols)
if G[r][c]==0 and (r==0 or c==0 or r==rows-1 or c==cols-1) ]
for r,c in leaks:
for dr,dc in [(-1,0),(1,0),(0,-1),(0,1)]: # offsets of neighbours
nr,nc = r+dr, c+dc # coordinates of a neighbour
if nr not in range(rows): continue # out of bounds
if nc not in range(cols): continue # out of bounds
if G[nr][nc] != 0: continue # Wall
if (nr,nc) in leaks: continue # already known
leaks.append((nr,nc)) # add new leak
return sum( row.count(0) for row in G) - len(leaks)
输出：
grid = [[1, 1, 1, 1, 1],
[1, 0, 0, 0, 1],
[1, 0, 0, 0, 1],
[1, 0, 0, 0, 1],
[1, 1, 1, 1, 1]]
print(water(grid)) # 9
grid = [[1, 1, 1, 0, 1],
[1, 0, 0, 0, 1],
[1, 0, 0, 0, 1],
[1, 0, 0, 0, 1],
[1, 1, 1, 1, 1]]
print(water(grid)) # 0
grid = [[1, 1, 1, 0, 1],
[1, 0, 1, 0, 1],
[1, 0, 1, 0, 1],
[1, 0, 1, 0, 1],
[1, 1, 1, 1, 1]]
print(water(grid)) # 3
请注意，这只会在水平和垂直(而不是对角线(方向上查找泄漏。要管理通过对角线的泄漏，需要将(-1，-1(、(-1，1(、(1，-1(和(1，1(添加到偏移列表中
删除从边缘开始的零，用一组复数(用于快速查找(表示零的坐标(用于方便邻居计算(：
def water(G):
m, n = len(G), len(G[0])
zeros = {complex(i, j)
for i in range(m) for j in range(n)
if G[i][j] == 0}
for z in list(zeros):
if z.real in (0, m-1) or z.imag in (0, n-1):
q = [z]
for z in q:
if z in zeros:
zeros.remove(z)
for a in range(4):
q.append(z + 1j**a)
return len(zeros)
或者使用Alain的单个BFS风格，用所有边零初始化队列：
def water(G):
m, n = len(G), len(G[0])
zeros = {complex(i, j)
for i in range(m) for j in range(n)
if G[i][j] == 0}
q = [z for z in zeros
if z.real in (0, m-1) or z.imag in (0, n-1)]
for z in q:
if z in zeros:
zeros.remove(z)
for a in range(4):
q.append(z + 1j**a)
return len(zeros)