图论07-被包围的区域(Java)

本文主要是介绍图论07-被包围的区域(Java)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

7.被包围的区域

题目描述

给你一个 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'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

题目分析

--题目分析：
解决被'X'包围的'O'区域的问题，通过将与边界相连的'O'标记为'A'，最后再将所有'O'修改为'X'，所有'A'修改为'O'来达到目的。下--思路分析
1.为了找到临海点，我们从四条边分别进行dfs搜索，
如果找到与海相邻的点“O”或者与海相邻的点“O”相邻的“O”点我们将其标记为“A”，表示此点不变为“X”2.通过四个边的dfs，我们已经将所以临海点均标记，此时重新遍历board数组，
将此时数组中的“O”(被包裹点)变为“X”,再将“A”还原为“O”即可

代码详解

1.首先检查输入的二维字符数组 board 是否为空或长度为 0，如果是，则直接返回，不进行任何操作。确定二维字符数组的行数 rows 和列数 cols。2.接下来，遍历第一列和最后一列，以及第一行和最后一行，针对边界上的 'O' 进行深度优先搜索。3.在 dfs(char[][] board, int i, int j) 方法中，实现深度优先搜索：
首先，检查当前位置是否超出边界或者不是 'O'，如果是，则直接返回。
将当前位置标记为 'A'，表示未被包围的区域。
继续向当前位置的四个方向进行递归深度优先搜索：向下、向上、向右、向左。4.完成所有深度优先搜索后，遍历整个二维数组：
将标记为 'O' 的位置改为 'X'，表示被包围的区域。
将标记为 'A' 的位置改回 'O'，表示未被包围的区域。

Java代码实现

     public void solve(char[][] board) {if (board == null || board.length == 0) {return;}int rows = board.length;int cols = board[0].length;// 遍历第一列和最后一列for (int i = 0; i < rows; i++) {dfs(board, i, 0);         // 从边界'O'开始深度优先搜索dfs(board, i, cols - 1);  // 从边界'O'开始深度优先搜索}// 遍历第一行和最后一行for (int j = 0; j < cols; j++) {dfs(board, 0, j);         // 从边界'O'开始深度优先搜索dfs(board, rows - 1, j);  // 从边界'O'开始深度优先搜索}// 恢复标记后的区域for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (board[i][j] == 'O') {board[i][j] = 'X';  // 被包围的区域} else if (board[i][j] == 'A') {board[i][j] = 'O';  // 未被包围的区域}}}}// 深度优先搜索函数private void dfs(char[][] board, int i, int j) {// 边界条件和终止条件if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != 'O') {return;}// 标记当前位置为'A'board[i][j] = 'A';// 继续向四个方向进行深度优先搜索dfs(board, i + 1, j);  // 向下搜索dfs(board, i - 1, j);  // 向上搜索dfs(board, i, j + 1);  // 向右搜索dfs(board, i, j - 1);  // 向左搜索}