Lintcode 477. Surrounded Regions

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.

Example

Example 1:

Input:
  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

Example 2:

Input:
  X X X X
  X O O X
  X O O X
  X O X X
Output:
  X X X X
  X O O X
  X O O X
  X O X X

Code (Java):

?

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

public class Solution {     /*      * @param board: board a 2D board containing 'X' and 'O'      * @return: nothing      */     public void surroundedRegions(char[][] board) {         if (board.length == 0 || board[0].length == 0) {             return;         }           int m = board.length;         int n = board[0].length;         boolean[][] visited = new boolean[m][n];           for (int i = 0; i < n; i++) {             surroundedRegionsHelper(0, i, board, visited);             surroundedRegionsHelper(m - 1, i, board, visited);         }           for (int i = 1; i < m - 1; i++) {             surroundedRegionsHelper(i, 0, board, visited);             surroundedRegionsHelper(i, n - 1, board, visited);         }           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] == 'Y') {                     board[i][j] = 'O';                 }             }         }     }       private void surroundedRegionsHelper(int row, int col, char[][] board, boolean[][] visited) {         int m = board.length;         int n = board[0].length;           if (row < 0 || row >= m || col < 0 || col >= n || visited[row][col]) {             return;         }           if (board[row][col] == 'X') {             return;         }           visited[row][col] = true;         board[row][col] = 'Y';           int[][] dirs = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};         for (int i = 0; i < 4; i++) {             surroundedRegionsHelper(row + dirs[i][0], col + dirs[i][1], board, visited);         }     } }