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