江苏龙网

  1. 首页 > 人文 > >

爱笑的姑娘|Python实战操作：解题之被围绕的区域

题目
给定一个二维的矩阵 ， 包含 ‘X’ 和 ‘O’（字母 O） 。
找到所有被 ‘X’ 围绕的区域 ， 并将这些区域里所有的 ‘O’ 用 ‘X’ 填充 。
示例:
X X X XX O O XX X O XX O X X运行你的函数后 ， 矩阵变为：
X X X XX X X XX X X XX O X X解释:
【爱笑的姑娘|Python实战操作：解题之被围绕的区域】被围绕的区间不会存在于边界上 ， 换句话说 ， 任何边界上的 ‘O’ 都不会被填充为 ‘X’ 。任何不在边界上 ， 或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’ 。 如果两个元素在水平或垂直方向相邻 ， 则称它们是“相连”的 。
爱笑的姑娘|Python实战操作：解题之被围绕的区域解题思路
思路：DFS、BFS
首先先看题目 ， 给定的二维矩阵中 ， 包含 ‘X’ 和 ‘O’（字母 O） 。 再看解释部分 ， 任何边界上的 ‘O’ 不会被填充为 ‘X’ ， 那么现在也就是说 ， 其实有三个部分：

  • 可形成包围的 ‘X’；
  • 被 ‘X’ 包围的 ‘O’；
  • 未被 ‘X’ 包围的 ‘O’ 。
现在题目的要求是将被包围的 ‘O’ ， 转变为 ‘X’ 。 前面也说了 ， 未被包围的 ‘O’ ， 是处于边界上的 ， 同时侧面说明与边界 ‘O’ 相连的 ‘O’ 又不会被 ‘X’ 填充 。
那么我们可以根据这个性质 ， 我们考虑从边界开始扩散 ， 先去标记不能被填充的 ‘O’ ， 也就是与边界 ‘O’ 相连的部分 ， 那么剩下的 ‘O’ 则会被包围转变为 ‘X’ 。 具体的做法如下：
  • 以边界的 ‘O’ 为起点 ， 标记与之相连或者间接相连的字母 ‘O’；
  • 当标记完上面部分的 ‘O’ ， 此时开始遍历矩阵 ， 去判断每个字母（注意：标记的为不会被替换的部分）：如果该字母是被标记的部分 ， 那么将其重新转换为 ‘O’；如果该字母是未被标记的部门 ， 那么将其转换为 ‘X’ 。
注意：题目要求的是原地修改 ， 那么我们标记的时候 ， 将与边界 ‘O’ 相连的部分（包括边界 ‘O’） ， 标记为 ‘M’ 。
我们现在使用深度优先搜索（DFS）和广度优先搜索（BFS）的方法来解决这个问题 。 具体的代码如下 。
代码实现
#深度优先搜索（DFS）class Solution:def solve(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""if not board or len(board)==0:returndef dfs(board, i, j):# 不处于矩阵内 ， 或者如果已经标记的话 ， 直接跳过if not (0<=i None:"""Do not return anything, modify board in-place instead."""if not board or len(board) == 0:returnm = len(board)n = len(board[0])from collections import dequequeue = deque()# bfs 不同于 dfs 顺着满足条件的方向继续搜索# bfs 满足条件的都要入队列# 先将边界的 'O' 入队for i in range(m):# 这里是二维矩阵的最左列与最右列if board[i][0] == 'O':queue.append((i, 0))if board[i][n-1] == 'O':queue.append((i, n-1))for j in range(n):# 这里是二维矩阵的第一行和最后一行if board[0][j] == 'O':queue.append((0, j))if board[m-1][j] == 'O':queue.append((m-1, j))# 现在开始出队 ， 目前里面的都是边界的 'O'# 出队的同时 ， 进行标记 ， 同时查找与边界 'O' 相连的部分入队while queue:x, y = queue.popleft()board[x][y] = 'M'# 查找相连部分for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:if 0


推荐阅读


上一篇：甜腻的嘴角|三足鼎立已破，华为高通联发科的三国杀，引发了高通的两重忧虑

下一篇：忘川彼岸|如何＂玩转＂4代双筒数码夜视仪？