被围绕的区域.md

被围绕的区域

给定一个二维的矩阵，包含X和O。
找到所有被X围绕的区域，并将这些区域里所有的O用X填充。
被围绕的区间不会存在于边界上，换句话说，任何边界上的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，然后对四个方向进行深度搜索，同样标记相连O为A，接下来对于矩阵的四个边界进行递归深度搜索，将所有与边界O相连的O标记为A，最后遍历矩阵，将矩阵中所有现在存在的O替换成X，即被包围的需要替换的O，然后将所有的A替换回O即可。

每日一题

https://github.com/WindrunnerMax/EveryDay

参考

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