被围绕的区域

给定一个二维的矩阵,包含XO
找到所有被X围绕的区域,并将这些区域里所有的OX填充。
被围绕的区间不会存在于边界上,换句话说,任何边界上的O都不会被填充为X。任何不在边界上,或不与边界上的O相连的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

解释

被围绕的区间不会存在于边界上,换句话说,任何边界上的O都不会被填充为X。任何不在边界上,或不与边界上的O相连的O最终都会被填充为X。如果两个元素在水平或垂直方向相邻,则称它们是相连的。

题解

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function(board) {
    var m = board.length;
    if(m === 0) return void 0;
    var n = board[0].length;
    var dfs = function(x, y){
        if(x<0 || y<0 || x>=m || y>=n || board[x][y] !== 'O') return void 0;
        board[x][y] = 'A';
        dfs(x + 1, y);
        dfs(x - 1, y);
        dfs(x, y + 1);
        dfs(x, y - 1);
    }

    for (let i = 0; i < m; i++) {
        dfs(i, 0);
        dfs(i, n - 1);
    }
    for (let i = 1; i < n - 1; i++) {
        dfs(0, i);
        dfs(m - 1, i);
    }
    for (let i = 0; i < m; i++) {
        for (let k = 0; k < n; k++) {
            if (board[i][k] == 'A') board[i][k] = 'O';
            else if (board[i][k] == 'O') board[i][k] = 'X';
        }
    }
    return void 0;
};

思路

注意到题目的解释,任何边界上的O都不会被填充为X,这句话的意思是,所有最终与边界处相连的O都不会被填充为X,注意此处的相连指的是如果两个元素在水平或垂直方向相邻,则称它们是相连的。根据解释,我们将所有边界上的O找到,然后进行深度递归,搜索所有和这个O相连的O,然后将这个O替换成其他字符,此处替换成了A,然后将矩阵中所有现在存在的O替换成X,即被包围的需要替换的O,然后将所有的A替换回O即可。首先获取矩阵的行数为m列数为n,然后定义dfs函数进行递归深度遍历,如果传递的下边不合法或者值不为O就返回,否则就将该值定义为A,然后对四个方向进行深度搜索,同样标记相连OA,接下来对于矩阵的四个边界进行递归深度搜索,将所有与边界O相连的O标记为A,最后遍历矩阵,将矩阵中所有现在存在的O替换成X,即被包围的需要替换的O,然后将所有的A替换回O即可。

每日一题

https://github.com/WindrunnerMax/EveryDay

参考

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