本文共 1622 字，大约阅读时间需要 5 分钟。

被围绕的区域

给定一个二维的矩阵，包含X和O。

示例

X X X XX O O XX X O XX O X X

运行你的函数后，矩阵变为：

X X X XX X X XX X X XX 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/