乐趣区

关于java:LeetCode130被围绕的区域

被围绕的区域

题目形容:给你一个 m x n 的矩阵 board,由若干字符 ‘X’ 和 ‘O’,找到所有被 ‘X’ 围绕的区域,并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例阐明请见 LeetCode 官网。

起源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权,非商业转载请注明出处。

解法一:递归法

首先,如果数组为空,不须要调整,间接返回。

而后,解决逻辑是从数组的四个边开始遍历,如果遇到和其连通的,则将相应地位的字符临时重置更新为 ’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();}
    }
}

【每日寄语】 把自大从你的字典里删去。不是每个人都能够成为凡人,但每个人都能够成为心田弱小的人,置信本人,找准本人的地位,你同样能够领有一个有价值的人生。

退出移动版