1+ package Algorithms .bfs ;
2+
3+ import java .util .LinkedList ;
4+ import java .util .Queue ;
5+
6+ //https://oj.leetcode.com/problems/surrounded-regions/
7+ public class Solve {
8+ public static void main (String []strs ) {
9+ char [][]board = {
10+ {'X' ,'O' ,'X' ,'O' ,'X' ,'O' },
11+ {'O' ,'X' ,'O' ,'X' ,'O' ,'X' },
12+ {'X' ,'O' ,'X' ,'O' ,'X' ,'O' },
13+ {'O' ,'X' ,'O' ,'X' ,'O' ,'X' }
14+ };
15+
16+ //solve(board);
17+ }
18+
19+ public void solve (char [][]board ) {
20+ if (board ==null ||board .length ==0 ||board [0 ].length ==0 ) {
21+ return ;
22+ }
23+
24+ int rows =board .length ;
25+ int cols =board [0 ].length ;
26+
27+ // the first line and the last line.
28+ for (int j =0 ;j <cols ;j ++) {
29+ bfs (board ,0 ,j );
30+ bfs (board ,rows -1 ,j );
31+ }
32+
33+ // the left and right column
34+ for (int i =0 ;i <rows ;i ++) {
35+ bfs (board ,i ,0 );
36+ bfs (board ,i ,cols -1 );
37+ }
38+
39+ // capture all the nodes.
40+ for (int i =0 ;i <rows ;i ++) {
41+ for (int j =0 ;j <cols ;j ++) {
42+ if (board [i ][j ] =='O' ) {
43+ board [i ][j ] ='X' ;
44+ }else if (board [i ][j ] =='B' ) {
45+ board [i ][j ] ='O' ;
46+ }
47+ }
48+ }
49+
50+ return ;
51+ }
52+
53+ public void bfs1 (char [][]board ,int i ,int j ) {
54+ int rows =board .length ;
55+ int cols =board [0 ].length ;
56+
57+ Queue <Integer >q =new LinkedList <Integer >();
58+ q .offer (i *cols +j );
59+
60+ while (!q .isEmpty ()) {
61+ int index =q .poll ();
62+
63+ // Index is out of bound.
64+ if (index <0 ||index >=rows *cols ) {
65+ continue ;
66+ }
67+
68+ int x =index /cols ;
69+ int y =index %cols ;
70+
71+ if (board [x ][y ] !='O' ) {
72+ continue ;
73+ }
74+
75+ board [x ][y ] ='B' ;
76+ q .offer (index +1 );
77+ q .offer (index -1 );
78+ q .offer (index +cols );
79+ q .offer (index -cols );
80+ }
81+ }
82+
83+ public void bfs (char [][]board ,int i ,int j ) {
84+ int rows =board .length ;
85+ int cols =board [0 ].length ;
86+
87+ Queue <Integer >q =new LinkedList <Integer >();
88+ q .offer (i *cols +j );
89+
90+ while (!q .isEmpty ()) {
91+ int index =q .poll ();
92+
93+ int x =index /cols ;
94+ int y =index %cols ;
95+
96+ if (board [x ][y ] !='O' ) {
97+ continue ;
98+ }
99+
100+ board [x ][y ] ='B' ;
101+ if (y <cols -1 ) {
102+ q .offer (index +1 );
103+ }
104+
105+ if (y >0 ) {
106+ q .offer (index -1 );
107+ }
108+
109+ if (x >0 ) {
110+ q .offer (index -cols );
111+ }
112+
113+ if (x <rows -1 ) {
114+ q .offer (index +cols );
115+ }
116+ }
117+ }
118+ }