LeetCode-130-被围绕的区域 LeetCode-130-被围绕的区域

被围绕的区域

题目描述：给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例说明请见LeetCode官网。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：递归法

【LeetCode-130-被围绕的区域】首先，如果数组为空，不需要调整，直接返回。
然后，处理逻辑是从数组的四个边开始遍历，如果遇到和其连通的，则将相应位置的字符暂时重置更新为'A'，具体处理逻辑如下：

从第一行、最后一行、第一列、最后一列的每一个字符开始处理；

判断如果当前坐标不在数组范围内或者当前坐标位置的值不是'O'，跳过不用处理；

判断当前坐标位置的值如果不是'O'，说明这个字符是和边上的'O'连通的，将值暂时更新为'A'；

然后递归处理当前位置的前后左右四个位置。

最后遍历数组，将数组中标记为'A'的更新为'O'，这些是和边上的连通也就是没有被'X'围着的；将数组中标记为'O'的更新为'X'，这些是和边上的不连通也就是完全被'X'围着的。

public class LeetCode_130 { private static int row, col; public static void solve(char[][] board) { // 如果数组为空，不需要调整，直接返回 if (board.length == 0) { return; } row = board.length; col = board[0].length; // 从第一行和最后一行开始处理 for (int i = 0; i < row; i++) { dfs(board, i, 0); dfs(board, i, col - 1); }// 从第一列和最后一列开始处理 for (int i = 1; i < col - 1; i++) { dfs(board, 0, i); dfs(board, row - 1, i); }for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (board[i][j] == 'A') { board[i][j] = 'O'; } else if (board[i][j] == 'O') { board[i][j] = 'X'; } } } }public static void dfs(char[][] board, int x, int y) { // 如果当前坐标不在数组范围内或者当前坐标位置的值不是'O'，跳过不用处理 if (x < 0 || x >= row || y < 0 || y >= col || board[x][y] != 'O') { return; } // 当前坐标位置的值不是'O'，说明这个字符是和边上的'O'连通的，将值暂时更新为'A' board[x][y] = 'A'; // 然后递归处理当前位置的前后左右四个位置 dfs(board, x + 1, y); dfs(board, x - 1, y); dfs(board, x, y + 1); dfs(board, x, y - 1); }public static void main(String[] args) { char[][] board = new char[][]{ {'X', 'X', 'X', 'X'}, {'X', 'O', 'O', 'X'}, {'X', 'X', 'O', 'X'}, {'X', 'O', 'X', 'X'} }; System.out.println("-----填充之前-----"); for (char[] chars : board) { for (char c : chars) { System.out.print(c); } System.out.println(); } System.out.println(); /** * 测试用例，期望输出: * XXXX * XXXX * XXXX * XOXX */ System.out.println("-----填充之后-----"); solve(board); for (char[] chars : board) { for (char c : chars) { System.out.print(c); } System.out.println(); } } }