-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSurroundedRegions.java
More file actions
101 lines (78 loc) · 2.33 KB
/
SurroundedRegions.java
File metadata and controls
101 lines (78 loc) · 2.33 KB
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
import java.util.LinkedList;
import java.util.Queue;
public class SurroundedRegions {
public static void solve(char[][] board) {
int m=board.length;
int n=board[0].length;
if(m==0){
return;
}
for(int i=0; i<m; i++){
if(board[i][0]=='O')
bfs(i,0, board);
if(board[i][n-1]=='O')
bfs(i,n-1,board);
}
for(int i=0; i<n; i++){
if(board[0][i]=='O')
bfs(0,i,board);
if(board[m-1][i]=='O')
bfs(m-1,i,board);
}
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
System.out.printf(board[i][j]+",");
}
System.out.println();
}
System.out.println();
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(board[i][j]=='E')
board[i][j]='O';
else if(board[i][j]=='O')
board[i][j]='X';
}
}
}
static class Node{
int x;
int y;
Node(int x1, int y1){ x =x1; y=y1;}
}
static void bfs(int row, int col, char[][] board ){
int m=board.length;
int nn=board[0].length;
//char X;
Queue<Node> qu = new LinkedList<Node>();
Node no = new Node(row,col);
qu.offer(no);
//--------------------------------
board[row][col]='E';
while(!qu.isEmpty()){
Node top = qu.poll();
int tX=top.x;
int tY=top.y;
if(tX!=0 && board[tX-1][tY]=='O'){
Node n = new Node(tX-1,tY);
qu.offer(n);
board[tX-1][tY]='E';
}
if(tX!=m-1 && board[tX+1][tY]=='O'){
Node n = new Node(tX+1,tY);
qu.offer(n);
board[tX+1][tY]='E';
}
if(tY!=0 && board[tX][tY-1]=='O'){
Node n = new Node(tX,tY-1);
qu.offer(n);
board[tX][tY-1]='E';
}
if(tY!=nn-1 && board[tX][tY+1]=='O'){
Node n = new Node(tX,tY+1);
qu.offer(n);
board[tX][tY+1]='E';
}
}
}
}