# 被围绕的区域
给定一个二维的矩阵，包含`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`。如果两个元素在水平或垂直方向相邻，则称它们是相连的。

## 题解

```javascript
/**
 * @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/
```