【算法分析与设计】被围绕的区域

��      个人主页：五敷有你      

 系列专栏：算法分析与设计

⛺️稳中求进，晒太阳

题目

给你一个 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"]]

思路（dfs+递归）

图中就有三种状态

• x
• 被x包围的O
• 没有被x包围的O

  体中要求把所有被x包围的O换成X,没有被X包围的O不用理会。

  那么想直接找被X包围O很难，因为被X包围的O不知有一个，可能连成片，所以想直接找上下左右判断不切时间，pass

  那就想到用边缘的O,来做深度优先遍历，这样，一路上所有的O都是不符合条件的，让他改为其他字符。

  之后遍历所有字符，找到O改为x，并将其他字符改回O。

  代码实现

  class Solution {    public void solve(char[][] board) {         int row=board.length;         int col=board[0].length;            for(int i=0;i