[华为OD] 污染水域(多源BFS)

**污染水域（多源BFS）**

在这个世界上，水是生命的源泉。然而，由于人类活动导致的污染，使得水变得越来越脏。作为一名程序员，我决定使用计算机算法来模拟和解决这个问题。

**问题描述**

我们有一个二维网格，每个格子代表一个水域区域。每个区域都有一个污染度，表示该区域的水质如何。我们的目标是找到从每个源头（代表清洁水源）到达所有其他区域的最短路径，并且在这个过程中尽量减少污染。

**算法描述**

我们将使用广度优先搜索（BFS）算法来解决这个问题。BFS 是一种图论算法，用于找到从一个点到另一个点的最短路径。在我们的例子中，我们需要从每个源头到达所有其他区域，并且在这个过程中尽量减少污染。

**代码实现**

from collections import dequeclass WaterPollution:
 def __init__(self, grid):
 self.grid = grid self.rows, self.cols = len(grid), len(grid[0])
 self.source = []
 for i in range(self.rows):
 for j in range(self.cols):
 if grid[i][j] ==1: #代表清洁水源 self.source.append((i, j))

 def pollution_bfs(self):
 directions = [(0,1), (0, -1), (1,0), (-1,0)]
 result = []
 for source in self.source:
 queue = deque([(source,0)]) # (位置，污染度)
 visited = set([source])
 while queue:
 position, pollution = queue.popleft()
 if position not in visited:
 visited.add(position)
 for direction in directions:
 new_position = (position[0] + direction[0], position[1] + direction[1])
 if0 <= new_position[0] < self.rows and0 <= new_position[1] < self.cols:
 new_pollution = pollution + self.grid[new_position[0]][new_position[1]]
 queue.append((new_position, new_pollution))
 result.append((source, new_position, new_pollution))
 return result# 测试用例grid = [
 [0,0,0,0],
 [0,2,2,0],
 [0,1,1,0],
 [0,0,0,0]
]

water_pollution = WaterPollution(grid)
result = water_pollution.pollution_bfs()
for item in result:
 print(item)

**注释**

* `WaterPollution` 类代表水域污染问题。
* `pollution_bfs` 方法使用广度优先搜索算法来找到从每个源头到达所有其他区域的最短路径，并且在这个过程中尽量减少污染。
* `directions` 列表定义了四个方向（上下左右）。
* `queue` 队列用于存储待处理的位置和污染度。
* `visited` 集合用于记录已经访问过的位置。
* 测试用例使用一个4x4 的网格来演示算法。

**结论**

在这个世界上，水是生命的源泉。然而，由于人类活动导致的污染，使得水变得越来越脏。在这个问题中，我们使用计算机算法来模拟和解决这个问题。通过广度优先搜索算法，我们可以找到从每个源头到达所有其他区域的最短路径，并且在这个过程中尽量减少污染。这是一个有趣的问题，需要深入理解图论算法和计算机编程。