1+ /*
2+ Author: Andy, nkuwjg@gmail.com
3+ Date: Jan 20, 2015
4+ Problem: Surrounded Regions
5+ Difficulty: Easy
6+ Source: http://leetcode.com/onlinejudge#question_130
7+ Notes:
8+ Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
9+ A region is captured by flipping all 'O's into 'X's in that surrounded region .
10+ For example,
11+ X X X X
12+ X O O X
13+ X X O X
14+ X O X X
15+ After running your function, the board should be:
16+ X X X X
17+ X X X X
18+ X X X X
19+ X O X X
20+
21+ Solution: Traverse from the boarder to the inside and mark all the 'O's that are not surrounded by 'X' as 'V' (visited).
22+ 1. BFS (queue).
23+ */
24+ public class Solution {
25+ public void solve (char [][]board ) {
26+ if (board .length ==0 ||board [0 ].length ==0 )return ;
27+ int M =board .length ,N =board [0 ].length ;
28+ for (int i =0 ;i <M ; ++i ) {
29+ for (int j =0 ;j <N ; ++j ) {
30+ if (i ==0 ||j ==0 ||i ==M -1 ||j ==N -1 ) {
31+ bfs (board ,i ,j );
32+ }
33+ }
34+ }
35+ for (int i =0 ;i <M ; ++i )
36+ for (int j =0 ;j <N ; ++j )
37+ board [i ][j ] = (board [i ][j ] =='V' ) ?'O' :'X' ;
38+ }
39+ public void bfs (char [][]board ,int row ,int col ) {
40+ if (board [row ][col ] !='O' )return ;
41+ int M =board .length ,N =board [0 ].length ;
42+ Queue <Integer >q =new LinkedList <Integer >();
43+ q .offer (row );q .offer (col );
44+ while (q .isEmpty () ==false ) {
45+ int i =q .poll ();int j =q .poll ();
46+ if (i <0 ||i ==M ||j <0 ||j ==N )continue ;
47+ if (board [i ][j ] !='O' )continue ;// important to recheck!
48+ board [i ][j ] ='V' ;
49+ q .offer (i -1 );q .offer (j );
50+ q .offer (i +1 );q .offer (j );
51+ q .offer (i );q .offer (j -1 );
52+ q .offer (i );q .offer (j +1 );
53+ }
54+ }
55+ }
