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

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

文章目录

• BFS与多源BFS
• 污染水域
• leetcode 1162:：地图分析
• leetcode 542：01矩阵
• leetcode 1020：飞地的数量

BFS与多源BFS

BFS广度优先搜索，BFS一般用队列实现，遵循着先进先出的原则，比较典型的例子就是之前说过的二叉树层序遍历。

在二叉树的层序遍历中，入口只有一个，也就是根节点。在遍历过程中，每次都拿出队列的第一个值，并把它的衍生值放在队列的最右边。

在二叉树的层序遍历中，从上往下一层一层走下去，不会出现一个节点重复出现的情况。

多源BFS，就像它的名称一样，有多个源头（也就是入口）。一般用在图中，以多个入口为起点，向周围进行遍历，因为从多个入口出发可能走到同一个位置，为了防止重复遍历，需要对遍历过的位置进行标记。

下面给出了《污染水域》的题解和一些相似的leetcode题目的代码。

污染水域

输入一行字符串，字符串可以转换为N*N的数组，数组可认为是一个水域，判断多少天后，水域被全部污染。
数组中只有1和0两个数，1表示污染，每天只可污染上下左右的水域，如果开始全部被污染或永远无法污染，则返回-1。

这个题就是一个很典型的多源BFS问题，首先要找到遍历的入口，也就是初始水域中为1的位置。将这些位置都加入队列。
如果水域中不存在1，或者水域中全是1，那么不需要再进行污染，直接返回-1。
我们从每个入口出现，向上下左右四个方向进行遍历，并标记。如果要遍历的位置已经被标记了，或者超过了水域的边界，那么就忽略。如果没有被标记，则把它加入队列中去。

我们一步一步地完成这个代码。

1. 获取输入，构造水域矩阵。
   在华为OD的题目中，输入需要自己获取，所以我们可以先构造一下输入的矩阵。

   link = list(map(int,input().split()))
   n = int(math.sqrt(len(link)))
   mat = [[0]*n for _ in range(n)]
   

2. 现在我们来找多源BFS中的源， 并把它存到一个队列中去。

   q = []
   for i in range(n):for j in range(n):mat[i][j] = link[i*n+j]if link[i*n+j]==1:  # 如果是污染区q.append([i,j])
   

3. 如果区域不存在污染或者全是污染，直接返回 - 1。

   if not q or len(q) == len(link):return -1
   

4. 定义一下遍历的方向，和最大天数。

   direction = [[1,0],[-1,0],[0,1],[0,-1]] # 四个方向
   max_num = 0    # 求最大天数，所以初始化为一个比较小的数
   

5. 开始遍历！

   while q: # 只要q中有东西就一直遍历cur  = q.pop(0) # 取出队列的第一个值x, y = cur # 当前位置for di in directions:  # 遍历四个方向newx = x+di[0]newy = y+di[1]if newx<0 or newy<0 or newx>=n or newy>=n:continue # 如果越界就跳过if mat[newx][newy]!=0:continue # 如果访问过就跳过mat[newx][newy] = mat[x][y]+1 # 标记当前位置，用的数字可以代表与污染区的距离【也就是扩散用的时间】if max_num < mat[newx][newy]:max_num = mat[newx][newy] # 更新最大天数q.append([newx,newy])
   return max_num-1 # 因为mat[x][y]的初始值是1，所以这里要-1
   

leetcode 1162:：地图分析

/

这道题也是一个典型的多源BFS。要求的是海洋单元到距离它最近的陆地单元格的距离是最大的，可以理解成我们已陆地单元格为源头，开始向四周遍历，最后访问到的海洋就是距离最远的海洋。

我们用海洋到陆地的距离来标记单元格，那么最后找到的海洋的标记，就代表了它到离它最近的陆地单元格的距离。

class Solution(object):def maxDistance(self, grid):""":type grid: List[List[int]]:rtype: int"""direction = [[-1,0],[1,0],[0,1],[0,-1]]q = []n = len(grid)for i in range(n):for j in range(n):if grid[i][j] == 1:q.append([i,j])if not q or len(q)==n**2:return -1while q:cur = q.pop(0)x,y = curfor di in direction:tmp_x = x + di[0]tmp_y = y + di[1]if tmp_x<0 or tmp_y<0 or tmp_x>=n or tmp_y>=n or grid[tmp_x][tmp_y]!=0:continuegrid[tmp_x][tmp_y] = grid[x][y]+1q.append([tmp_x,tmp_y])return grid[cur[0]][cur[1]]-1

leetcode 542：01矩阵

/

求每一个非0元素到最近的0的距离。可以理解成以0为起点，向周围扩散，并用起到到当前位置的距离进行标记。要返回的是距离矩阵，其实就是被标记后的矩阵。

class Solution(object):def updateMatrix(self, matrix):""":type mat: List[List[int]]:rtype: List[List[int]]"""q = []m = len(matrix)n = len(matrix[0])for i in range(m):for j in range(n):if matrix[i][j]==0:q.append([i,j])else:matrix[i][j] = -1direction = [[1,0],[-1,0],[0,1],[0,-1]]while q:cur = q.pop(0)x,y = curfor di in direction:newx = x+di[0]newy = y+di[1]if newx<0 or newy<0 or newx>=m or newy>=n or matrix[newx][newy]!=-1:continuematrix[newx][newy] = matrix[x][y]+1q.append([newx,newy])return matrix

leetcode 1020：飞地的数量

/

找到无法离开网格边界的陆地单元格的数量，就是找没有和边界相连的陆地单元格的数量。我们可以换个思路，找到所有与边界相连的陆地单元格，并把它们置0，那么剩下的陆地单元格就是不相连的。

我们的源就是边界上的陆地单元格，以此为入口向四个方向遍历。

class Solution(object):def numEnclaves(self, grid):""":type grid: List[List[int]]:rtype: int"""m = len(grid)n = len(grid[0])if m<=2 or n<=2:return 0q = []for i in range(m):if grid[i][0]==1:q.append([i,0])if grid[i][n-1]==1:q.append([i,n-1])for j in range(1,n-1):if grid[0][j] == 1:q.append([0,j])if grid[m-1][j] ==1:q.append([m-1,j])direction = [[-1,0],[1,0],[0,1],[0,-1]]while q:cur = q.pop(0)x,y = curgrid[x][y] = 0for di in direction:newx = x+di[0]newy = y+di[1]if newx<0 or newy<0 or newx>=m or newy>=n or grid[newx][newy]==0:continuegrid[newx][newy] = 0q.append([newx,newy])return sum([sum(grid[i]) for i in range(m)])