Surrounded area

Title Description ：

Given a two-dimensional matrix , contain ‘X’ and ‘O’（ Letter O）.

Find all the victims ‘X’ The surrounding area , And put all of these areas ‘O’ use ‘X’ fill .

---

Thought analysis ：

This question is particularly similar to the number of islands , The difficulty of this problem lies in The boundary of the 0 And internal multiple 0 Handling of the connectivity of , Here's the picture ：

Bottom boundary 0 And internal 0 It's connected , So there is no need to put these 0 Change it to X.

（1） We can make the boundary dfs Traverse , Connect all connected 0 find , Change to letter ‘A’;
（2） Traversal array , Element encountered ’0’, Change it to ’X’, Element encountered ‘A’, Change it to ’0’

You know ‘A’ There is no need to modify , So change it back .

---

Reference code ：

public void solve(char[][] board) {
    
  if(board == null || board.length == 0)return;
  int m = board.length;
  int n = board[0].length;
  // All the left and right boundaries 0 The connectivity of is changed to 'A'
  for(int i = 0; i < m; i++){
    
     dfs(board, i, 0);
     dfs(board, i, n - 1);
  }

  // All of the upper and lower boundaries 0 The connectivity of is changed to 'A'
  for(int i = 1; i < n - 1; i++){
    // Note here , When calculating above, put i=0 and i=n-1 It's all calculated 
     dfs(board, 0, i);
     dfs(board, m - 1, i);
  }
  // take ‘A’ Change back ‘O’, To be changed ‘O’ Change it to ‘X’
  for(int i = 0; i < m; i++){
    
    for(int j = 0; j < n; j++){
    
      if(board[i][j] == 'A')board[i][j] = 'O';
      else if(board[i][j] == 'O')board[i][j] = 'X';
    }
  }
}

//dfs Find all 0 Connected element , Change it to ‘A’
public void dfs(char[][] board, int i, int j){
    
  if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'O')return;// Note here ： Can not write board[i][j] == 'X'
  if(board[i][j] == 'O')board[i][j] = 'A';// Key code 
  dfs(board, i + 1, j);
  dfs(board, i - 1, j);
  dfs(board, i, j + 1);
  dfs(board, i, j - 1);
}

---

Summary ：

dfs In the judgment condition ：board[i][j] != 'O’ It can't be changed to board[i][j] == ‘X’, If it is changed to the latter , Then for the following cases , Will all ‘O’ Change it to ‘A’ after ,board[i][j] == 'X’ To return to , because ‘A’ != ‘X’, So recursion will continue ：

---

Similar topics ：

LeetCode Number of Islands

LeetCode463 The perimeter of the island