本文讲述了python基础编程100例：第75期-基础算法：广度优先搜索 被围绕的区域！具有很好的参考价值，希望对大家有所帮助。一起跟随六星小编过来看看吧，具体如下:

第75期-基础算法：广度优先搜索 被围绕的区域

1 问题描述

被围绕的区域 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例 1:

输入: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

输出: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

解释: 被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例 2:

输入: board = [["X"]]

输出: [["X"]]

示例 3:

输入: board = [['O', 'O'], ['O', 'O']]

输出: [['O', 'O'], ['O', 'O']]

初始代码

from typing import List

class Solution:

    def solve(self, board: List[List[str]]) -> None:

        #在此之间填写代码

print(Solution().solve([["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]))

print(Solution().solve([["X"]]))

print(Solution().solve([["O","O"],["O","O"]]))

2 解题思路

标签：广度优先搜索 / 深度优先搜索

从边界出发吧，先把边界上和 O 连通点找到, 把这些变成 B

然后遍历整个 board 把 O 变成 X, 把 B 变成 O

如下图所示：

3 解题方法

from typing import List

class Solution:

    def solve(self, board: List[List[str]]) -> None:

        a,b=len(board),len(board[0])

        queue=[]

        i,x=0,0

        while i < a:

            if board[i][x]=='O':queue.append((i,x))

            i+=1

            if i==a and x!=b-1:

                i=0

                x=b-1

        i,x=0,0

        while i < b:

            if board[x][i]=='O':queue.append((x,i))

            i+=1

            if i==b and x!=a-1:

                i=0

                x=a-1

        while queue:

            cur=queue.pop(0)

            for i in ((1,0),(0,1),(-1,0),(0,-1)):

                x,y=cur[0]+i[0],cur[1]+i[1]

                if 0<=x<a and 0<=y<b and board[x][y]=='O':

                    queue.append((x,y))

            board[cur[0]][cur[1]]='B'

        

        for i in range(a):

            for j in range(b):

                if board[i][j]=='O':board[i][j]='X'

                if board[i][j]=='B':board[i][j]='O'

        return board

print(Solution().solve([["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]))

print(Solution().solve([["X"]]))

print(Solution().solve([["O","O"],["O","O"]]))

第1-3，35-37行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑

第4行： 定义变量a，b用于存放矩阵的长度和宽度

第5行： 定义列表queue用于存放接下来需要遍历的坐标

第6行： 定义变量i，x用于遍历矩阵边界的点的坐标

第7-19行： 将矩阵边界上所以等于'O'的点放进queue中

第21行： 判断queue列表是否为空，若不为空则还有坐标需要遍历，继续循环

第22行： 定义坐标cur用于存放queue接下来需要使用的第一个坐标并从queue中删除该坐标

第23行： 使用for循环遍历上下左右四个方向

第24行： 定义变量x，y用于存放该方向的横竖坐标

第25行： 判断该点横竖坐标是否在矩阵内且该点是否等于'O'

第26行： 若满足条件，则在queue队列中加如带点坐标，用于之后该点扩散

第14行： 将之前的点变成'B'防止下次循环又加上他

第29-32行： 重新遍历矩阵，将所有的'O'变成'X'，将所有的'B'变成'O'

第33行： 返回修改后的矩阵

代码运行结果为：

算法讲解

这里用到了基础算法：广度优先搜索，简单讲解下这个算法：

广度优先搜索

广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域，故得名。

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

如果你想用Python开辟副业赚钱，但不熟悉爬虫与反爬虫技术，没有接单途径，也缺乏兼职经验
关注下方微信公众号：Python编程学习圈，获取价值999元全套Python入门到进阶的学习资料以及教程，还有Python技术交流群一起交流学习哦。