130-. Surrounded Regions Total Accepted: 55559 Total Submissions: 339215 Difficulty: Medium Given a 2D board containing ‘X’ and ‘O’, capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

For example, X X X X X O O X X X O X X O X X After running your function, the board should be:

X X X X X X X X X X X X X O X X Hide Tags Breadth-first Search Union Find Hide Similar Problems (M) Number of Islands (M) Walls and Gates

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88


package matrix;

public class SurrounedRegions {

// https://leetcode.com/discuss/59652/java-boundary-turning-solution-simple-clean-code-commented
 public void solve(char[][] board) {
  int m = board.length;
  int n = board[0].length;
  if (m < 2 || n < 2) 
   return;
  
  //Any 'O' connected to a boundary can't be turned to 'X', so ...
  //start from first row to last row, turn 'O' to '*'
  for (int i = 0; i < m; i++) {
   if (board[i][0] == 'O') {
    boundaryDFS(board, i, 0);
   }
   if (board[i][n-1] == 'O') {
    boundaryDFS(board, i, n-1);
   }
  }
        
        // start from first column to last column, turn 'O' to '*'
  for (int j = 0; j < n; j++) {
   if (board[0][j] == 'O') {
    boundaryDFS(board, 0, j);
   }
   if (board[m-1][j] == 'O') {
    boundaryDFS(board, m-1, j);
   }
  }
        
  // post-processing, turn 'O' to 'X', '*' back to 'O',  keep 'X' intact.
  for (int i= 0; i < m; i++) {
   for (int j = 0; j < n; j++) {
    if (board[i][j] == 'O') {
     board[i][j] = 'X';
    } else if (board[i][j] == '*') {
     board[i][j] = 'O';
    }
   }
  }
  
 }

 //Use DFS algo to turn internal however boundary-connected 'O' to '*';
 public void boundaryDFS(char[][] board, int i, int j) {
  if (i < 0 || i > board.length - 1 || j < 0 || j > board[0].length - 1) 
   return;
  
  if (board[i][j] == 'O') {
   board[i][j] = '*';
  }
  
  if (i > 1 && board[i - 1][j] == 'O') {
   boundaryDFS(board, i-1, j);
  }
  
  if (i < board.length - 2 && board[i + 1][j] == 'O') {
   boundaryDFS(board, i+1, j);
  }
  if (j > 1 && board[i][j - 1] == 'O') {
   boundaryDFS(board, i, j - 1);
  }
  if (j < board[0].length - 2 && board[i][j + 1] == 'O') {
   boundaryDFS(board, i, j + 1);
  } 
 }

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  char[][] board = { { 'X', 'X', 'X', 'X' }, { 'X', 'O', 'O', 'X' }, { 'X', 'X', 'O', 'X' },
    { 'X', 'O', 'X', 'X' } };

  SurrounedRegions sr = new SurrounedRegions();
  sr.solve(board);
  sr.printMatrix(board);

 }
 
 public void printMatrix(char[][] board) {
  for (char[] cells : board) {
   System.out.println(" "+ String.valueOf(cells)); 
  }
 }

}