130. 被围绕的区域

题目

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

题解

这道题用到了三个知识点，bfs、dfs回溯。
第一个知识点
深度优先搜索（depth-first seach，DFS）在搜索到一个新的节点时，立即对该新节点进行遍
历；因此遍历需要用先入后出的栈来实现，也可以通过与栈等价的递归来实现。对于树结构而言，
由于总是对新节点调用遍历，因此看起来是向着“深”的方向前进。
深度优先搜索也可以用来检测环路：记录每个遍历过的节点的父节点，若一个节点被再次遍
历且父节点不同，则说明有环。也可以用拓扑排序判断是否有环路，若最后存
在入度不为零的点，则说明有环。
有时我们可能会需要对已经搜索过的节点进行标记，以防止在遍历时重复搜索某个节点，这
种做法叫做状态记录或记忆化（memoization）。

第二个知识点。

回溯法（backtracking）是优先搜索的一种特殊情况，又称为试探法，常用于需要记录节点状
态的深度优先搜索。通常来说，排列、组合、选择类问题使用回溯法比较方便。

顾名思义，回溯法的核心是回溯。在搜索到某一节点的时候，如果我们发现目前的节点（及
其子节点）并不是需求目标时，我们回退到原来的节点继续搜索，并且把在目前节点修改的状态还原。这样的好处是我们可以始终只对图的总状态进行修改，而非每次遍历时新建一个图来储存
状态。在具体的写法上，它与普通的深度优先搜索一样，都有 [修改当前节点状态]→[递归子节
点] 的步骤，只是多了回溯的步骤，变成了 [修改当前节点状态]→[递归子节点]→[回改当前节点
状态]。

记住两个小诀窍，一是按引用传状态，二是所有的状态修改在递归完成后回改。
回溯法修改一般有两种情况，一种是修改最后一位输出，比如排列组合；一种是修改访问标
记，比如矩阵里搜字符串。

第三个知识点。
广度优先搜索（breadth-first search，BFS）不同与深度优先搜索，它是一层层进行遍历的，因
此需要用先入先出的队列而非先入后出的栈进行遍历。由于是按层次进行遍历，广度优先搜索时
按照“广”的方向进行遍历的，也常常用来处理最短路径等问题。

深度优先搜索和广度优先搜索都可以处理可达性问题，即从一个节点开始是否
能达到另一个节点。因为深度优先搜索可以利用递归快速实现，很多人会习惯使用深度优先搜索
刷此类题目。可能产生栈溢出的情况；而用栈实现的深度优先搜索和用队列实现的广度优先搜索在写法上并没有太
大差异，因此使用哪一种搜索方式需要根据实际的功能需求来判断。

回到本题上来

先从最外侧填充，然后再考虑里侧。

coding

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */

var solve = function(board) {
  const col = board.length, column = col ? board[0].length : 0;
  for(let i = 0; i < col; i++) {
      for(let j = 0; j < column; j++) {
          const isEdge = i === 0 || j === 0 || i === col -1 || j === column -1;
          if(isEdge && board[i][j] === "O") {
              bfs(board, i, j, col, column); 
          }
      }
  }
  for(let i = 0; i < col; i++) {
      for(let j = 0; j < column; j++) {
        if(board[i][j] === "O") board[i][j] = "X";
         if(board[i][j] === '#') board[i][j] = "O";
      }
  }
  return board;
};
//  // dfs 递归
// const direction = [-1, 0, 1, 0, -1];
// const bfs = (board, i, j, col, column) => {
//     if((i < 0) || (j < 0) || (i >= col) || (j >= column) || (board[i][j] === '#') || (board[i][j] === 'X')){
//         return;
//      } 
//     board[i][j] = '#';
//     for(let c = 0; c < 4; c++) {
//         let dx = i + direction[c], dy = j + direction[c+1];
//         bfs(board, dx, dy, col, column);
//     }
// }

const direction = [-1, 0, 1, 0, -1];
const bfs = function(board, i, j) {
    const stack = [];
    stack.push([i, j]);
    board[i][j] = '#'
    while(stack.length) {
    //  // dfs 栈
    //     const [x, y] = stack[stack.length-1] // 某个方向状态维护不变
    //     if(x - 1 >= 0 && board[x-1][y] === 'O') {
    //         stack.push([x-1, y]);
    //         board[x-1][y] = '#';
    //         continue;
    //     }
    //     if(x + 1 <= board.length - 1 && board[x+1][y] === 'O') {
    //         stack.push([x+1, y]);
    //         board[x+1][y] = '#';
    //         continue;
    //     }  
    //    if(y - 1 >= 0 && board[x][y-1] === 'O') {
    //        stack.push([x, y-1]);
    //         board[x][y-1] = '#';
    //         continue;
    //     } 
    //     if(y + 1 < board[0].length && board[x][y+1] === 'O') {
    //         stack.push([x, y+1]);
    //         board[x][y+1] = '#';
    //         continue;
    //     }  
    //     stack.pop();  // 如果上下左右都搜索不到,本次搜索结束，弹出stack
    //  // bfs 队列
        const [x, y] = stack.shift();
        for(let c = 0; c < 4; c++) {
            let dx = x + direction[c], dy = y + direction[c+1];
            if((dx < 0) || (dy < 0) || (dx >= board.length) || (dy >= board[0].length) || (board[dx][dy] === '#') || (board[dx][dy] === 'X')){
               continue;
            } 
            board[dx][dy] = '#';
            stack.push([dx, dy]);
        }  
     } 
    }

复制代码