美文网首页
LeetCode 130. 被围绕的区域

LeetCode 130. 被围绕的区域

作者: phantom34 | 来源:发表于2019-06-28 14:45 被阅读0次

    题目链接

    https://leetcode-cn.com/problems/surrounded-regions/

    题目描述

    给定一个二维的矩阵,包含 'X' 和 'O'(字母 O)。
    找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O' 用 'X' 填充。
    示例:
    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

    题解

    题目意思就是只要被X所包围的地方将被吃掉,就像下围棋一样,而在边缘的O相当于围三缺一实际上是一片活棋也就保留了下来。
    于是我们只要找出所有与四边所在的O以及与其相连的O标记为任意字符,剩余O皆是被X所包围的,也就是会被X填充

    代码

    public void solve(char[][] board) {
            int length = board.length;
            if (length == 0)
                return;
            int rowLength = board[0].length;
            for (int i = 0; i < length; i++) {
                if (board[i][0] == 'O') {
                    dfs(i, 0, board);
                }
                if (board[i][rowLength - 1] == 'O') {
                    dfs(i, rowLength - 1, board);
                }
    
            }
    
            for (int i = 0; i < rowLength; i++) {
                if (board[0][i] == 'O') {
                    dfs(0, i, board);
                }
                if (board[length - 1][i] == 'O') {
                    dfs(length - 1, i, board);
                }
    
            }
    
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < rowLength; j++) {
                    if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                    if (board[i][j] == 'Y')
                        board[i][j] = 'O';
                }
            }
        }
    
        public void dfs(int x, int y, char[][] map) {
            if (x >= 0 && x < map.length && y >= 0 && y < map[0].length) {
                if (map[x][y] == 'O') {
                    map[x][y] = 'Y';
                    dfs(x - 1, y, map);
                    dfs(x + 1, y, map);
                    dfs(x, y - 1, map);
                    dfs(x, y + 1, map);
                }
            }
        }
    

    结果

    image.png

    相关文章

      网友评论

          本文标题:LeetCode 130. 被围绕的区域

          本文链接:https://www.haomeiwen.com/subject/cngscctx.html