leetcode 130. Surrounded regions (medium)

One 、 The main idea of the topic

label :  Search for

https://leetcode.cn/problems/surrounded-regions

To give you one  m x n  Matrix  board , Consists of several characters  'X'  and  'O' , Find all the victims  'X'  The surrounding area , And put all of these areas  'O'  use  'X'  fill .

Example  1：

Input ：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]] Output ：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]] explain ： The surrounding area does not exist on the boundary , let me put it another way , On any boundary  'O'  Will not be filled with  'X'.  Anything not on the border , Or not with the boundary  'O'  Connected  'O'  It will be filled with  'X'. If two elements are adjacent horizontally or vertically , They are “ Connected to a ” Of .

Example  2：

Input ：board = [["X"]] Output ：[["X"]]

Tips ：

• m == board.length

• n == board[i].length

• 1 <= m, n <= 200

• board[i][j]  by  'X'  or  'O'

Two 、 Their thinking

Find the connection component problem DFS To do it , Mainly the optimization of details . You can start from this place , Anything that is not on the boundary O Will become X. You can also reverse your thinking to find the one that is not surrounded . Specific implementation ideas ： Starting from the border , Look for the one connected with the border O, Mark it as a special value , And then put the others in the grid O Marked as X, Finally, mark the first step with a special value O Restore

3、 ... and 、 How to solve the problem

3.1 Java Realization

public class Solution {
 public void solve(char[][] board) {
 this.m = board.length;
 if (this.m == 0) {
 return;
 }
 this.board = board;
 this.n = board[0].length;

 for (int y = 0; y < m; y++) {
 dfs(0, y);
 dfs(n - 1, y);
 }

 for (int x = 0; x < n; x++) {
 dfs(x, 0);
 dfs(x, m - 1);
 }

 Map<Character, Character> v = new HashMap<>();
 v.put('G', 'O');
 v.put('O', 'X');
 v.put('X', 'X');
 for (int y = 0; y < m; y++) {
 for (int x = 0; x < n; x++) {
 switch (board[y][x]) {
 case 'G':
 board[y][x] = 'O';
 break;
 case 'O':
 board[y][x] = 'X';
 break;
 case 'X':
 board[y][x] = 'X';
 }
 }
 }
 }

 private char[][] board;
 private int m;
 private int n;

 private void dfs(int x, int y) {
 if (x < 0 || x >= n || y < 0 || y >= m || board[y][x] != 'O') {
 return;
 }
 board[y][x] = 'G';
 dfs(x - 1, y);
 dfs(x + 1, y);
 dfs(x, y - 1);
 dfs(x, y + 1);
 }
}


Four 、 Summary notes

• 2022/6/10  For connecting component problems DFS