Saturday, March 16, 2019

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):
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);
        }
    }
}

No comments:

Post a Comment