130. The surrounding area

The title

Given an m x n matrix board, consisting of characters’ x ‘and ‘O’, find all the regions surrounded by’ x ‘and fill all the ‘O’ in those regions with’ x ‘.

Answer key

This problem uses three knowledge points, BFS, DFS backtracking. The first knowledge point is depth-first seACH (DFS). When a new node is found, the new node is traversed immediately. So traversal needs to be done with a first-in, last-out stack, or it can be done with a recursion equivalent to the stack. For a tree structure, it looks like it’s going “deep” because it’s always traversing new nodes. Depth-first search can also be used to detect loops by recording the parent nodes of each traversed node. If a node is traversed again and the parent nodes are different, a loop is present. Topological sorting can also be used to determine whether there is a loop. If the end is stored at a point where the entry degree is not zero, it indicates that there is a loop. Sometimes we may need to mark already searched nodes to prevent repeated searches of a node over time, a practice called state recording or memoization.

Second point.

Backtracking is a special case of priority search, also known as heuristic method, which is often used in depth-first search where nodal states need to be recorded. Generally speaking, it is convenient to use backtracking method for permutation, combination and selection problems.

As the name implies, the core of backtracking is backtracking. When searching for a node, if we find that the current node (and its children) is not the demand target, we can go back to the original node to continue searching and restore the modified state of the current node. The advantage of this is that we can always modify only the overall state of the graph, rather than creating a new graph to store the state each time we traverse. In terms of the specific writing, it is the same as the common depth-first search, which has the steps of [modify the current node state]→[recursive sub-node], but with more backtracking steps, it becomes [modify the current node state]→[recursive sub-node]→[change the current node state].

Two tips to remember are to pass the state by reference and to revert all state changes after the recursion is complete. There are generally two cases of backtracking modification. One is to modify the last bit of output, such as permutation and combination; One is to modify the access notation, such as the search string in the matrix.

The third point. Breadth first search (BFS) is different from depth-first search, which is traversed layer by layer, so it needs to traverse with first-in, first-out queue instead of first-in, last-out stack. Because it traverses by hierarchy, breadth-first search traverses in the direction of “wide”, and is often used to deal with problems such as shortest paths.

Both depth-first search and breadth-first search can deal with the issue of accessibility, that is, whether starting from one node can reach the other node. Because depth-first searches can be implemented quickly using recursion, many people are used to using depth-first search brushes. Stack overflow may occur; There is not much difference between stack depth-first search and queue breadth-first search, so which search method to use needs to be determined according to the actual functional requirements.

Back to the subject

Fill in the outermost part first, and then consider the insides.

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] === The '#') board[i][j] = "O"; }}return board;
};
// // DFS recursion
// 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] = The '#'
    while(stack.length) {
    / / / / DFS stack
    // 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(); // If the search fails, the search ends and the stack pops up
    // // BFS queue
        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] === The '#') || (board[dx][dy] === 'X')) {continue;
            } 
            board[dx][dy] = The '#'; stack.push([dx, dy]); }}}Copy the code