Given a 2D board containing
'X' and 'O' (the letter 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
Code:
class Solution {
2
int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
3
public void solve(char[][] board) {
4
if (board.length == 0 || board[0].length == 0) return;
5
6
for (int i = 0;i < board.length;i++){
7
if (board[i][0] == 'O') helper(board,i,0);
8
if (board[i][board[0].length - 1] == 'O') helper(board,i,board[0].length - 1);
9
}
10
for (int j = 0; j< board[0].length;j ++){
11
if (board[0][j] == 'O') helper(board,0,j);
12
if (board[board.length - 1][j] == 'O') helper(board,board.length - 1,j);
13
}
14
for (int i = 0;i < board.length;i++){
15
for (int j = 0;j < board[0].length;j++){
16
if (board[i][j] == 'O') board[i][j] = 'X';
17
if (board[i][j] == '$') board[i][j] = 'O';
18
}
19
}
20
}
21
private void helper(char[][] board,int i,int j){
22
board[i][j] = '$';
23
/*for (int[] d:dir){
24
int x = i + d[0];
25
int y = j + d[1];
26
if (x >= 0 && x < board.length && y >=0 && y < board[0].length && board[x][y] == 'O')
27
helper(board,x,y);
28
} */
29
30
31
if (i > 1 && board[i-1][j] == 'O')
32
helper(board, i-1, j);
33
if (i < board.length - 2 && board[i+1][j] == 'O')
34
helper(board, i+1, j);
35
if (j > 1 && board[i][j-1] == 'O')
36
helper(board, i, j-1);
37
if (j < board[i].length - 2 && board[i][j+1] == 'O' )
38
helper(board, i, j+1);
39
}
40
}
No comments:
Post a Comment