-
Notifications
You must be signed in to change notification settings - Fork 0
/
Leetcode0130_BFS.java
65 lines (63 loc) · 2.03 KB
/
Leetcode0130_BFS.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
57
58
59
60
61
62
63
64
65
import java.awt.Point;
class Solution {
public void solve(char[][] board) {
if (board == null || board.length==0 || board[0] == null){
return;
}
int rowNum = board.length;
int colNum = board[0].length;
// System.out.println(rowNum);
// System.out.println(colNum);
Queue<Point> queue = new LinkedList<Point>();
for(int j=0;j<colNum; j++){
if (board[0][j]=='O'){
queue.offer(new Point(0,j));
}
if (board[rowNum-1][j]=='O'){
queue.offer(new Point(rowNum-1, j));
}
}
for (int i=0; i<rowNum; i++){
if (board[i][0]=='O'){
queue.offer(new Point(i,0));
}
if (board[i][colNum-1]=='O'){
queue.offer(new Point(i, colNum-1));
}
}
while(!queue.isEmpty()){
Point currNode = queue.poll();
int i = currNode.x;
int j = currNode.y;
if (board[i][j] == 'O'){
board[i][j] = '+';
// visit its neighbors
if (i-1>=0 && board[i-1][j] == 'O'){
queue.offer(new Point(i-1, j));
}
if (i+1<rowNum && board[i+1][j]=='O'){
queue.offer(new Point(i+1, j));
}
if (j-1>=0 && board[i][j-1]=='O'){
queue.offer(new Point(i,j-1));
}
if (j+1<colNum && board[i][j+1]=='O'){
queue.offer(new Point(i, j+1));
}
}
}
// scan board to flip all 'O' to 'X' and convert
// '+' back to 'O'
for (int i=0;i<rowNum;i++){
for(int j=0;j<colNum;j++){
if (board[i][j] == 'O'){
board[i][j] = 'X';
}
if (board[i][j] == '+'){
board[i][j] = 'O';
}
}
}
return ;
}
}