給定一些由 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 個單位的水。
我真的不確定如何開始解決這個問題。是否有任何演算法對此有幫助？我在考慮深度優先搜索或某種洪水填充，但現在我不確定這些是否適用于這個練習。
uj5u.com熱心網友回復：
您可以從邊緣的 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) 添加到偏移量串列中。
uj5u.com熱心網友回復：
從邊緣開始去除零，用一組（用于快速查找）復數（便于鄰居計算）表示零的坐標：
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)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/388158.html
上一篇：感知器演算法混亂
下一篇：最小洗掉子陣列以使陣列等于目標