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); // 向左搜索
}