深度搜索 - 被围绕的区域 - 《数据结构与算法》

题目
思路分析

题目

题目来源：力扣（LeetCode

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例 1：

输入：board = [[“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’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例 2：

输入：board = [[“X”]]
输出：[[“X”]]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 ‘X’ 或 ‘O’

思路分析

本题要求将所有被字母 X 包围的字母 O 都变为字母 X ，但很难判断哪些 O 是被包围的，哪些 O 不是被包围的。
注意到题目解释中提到：任何边界上的 O 都不会被填充为 X。我们可以想到，所有的不被包围的 O 都直接或间接与边界上的 O 相连。我们可以利用这个性质判断 O 是否在边界上，具体地说：

对于每一个边界上的 O，我们以它为起点，标记所有与它直接或间接相连的字母 O；
最后我们遍历这个矩阵，对于每一个字母：
- 如果该字母被标记过，则该字母为没有被字母 X 包围的字母 O，我们将其还原为字母 O；
- 如果该字母没有被标记过，则该字母为被字母 X 包围的字母 O，我们将其修改为字母 X。 ```javascript const solve = (board) => { // 行数 const m = board.length; if (m == 0) return; // [] 情况的特判 // 列数 const n = board[0].length; // 用深度搜索将边界上的字母O 以及与其直接或间接相连的字母O 标记成字母 NO // i: 行 // j: 列 const dfs = (i, j) => { if (i < 0 || i == m || j < 0 || j == n) return; // 越界了 // 遇到O，染为NO if (board[i][j] == ‘O’) {
```
   board[i][j] = 'NO';
   // 对四个方向的邻居进行dfs，判断是否为 O
   dfs(i + 1, j); // 下一行
   dfs(i - 1, j); // 上一行
   dfs(i, j + 1); // 右边一列
   dfs(i, j - 1); // 左边一列
```
  } };
  
  //从边界上的字母O 开始，深搜完成标记 for (let i = 0; i < m; i++) { // 遍历行 for (let j = 0; j < n; j++) { // 遍历列
```
   // i == 0  第一行
   // i == m - 1 最后一行
   // j == 0 第一列
   // j == n - 1 最后一列
   if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
       // 从最外层的字母O，开始DFS，将字母O 标记成 NO
       if (board[i][j] == 'O') dfs(i, j); 
   }
```
  } }
  
  // 遍历这个矩阵，对于每一个字母： // 如果该字母被标记过，则该字母为没有被字母 X 包围的字母 O，将其还原为字母 O // 如果该字母没有被标记过，则该字母为被字母 X 包围的字母 O，将其修改为字母 X for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) {
```
   if (board[i][j] === 'NO') board[i][j] = 'O'; // 恢复为大O
   else if (board[i][j] === 'O') board[i][j] = 'X'; // 小O变为X
```
  } } };

```