Surrounded Regions

Given a 2D board containing 'X' and '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

Analysis:

only the O's connected to O on edges are not surrounded by X. Then basic idea is to 

start from O's on edges, and do DFS to find all adjacent Os. Adjacency list would 

do the work but requires extra space. In space marking will save the extra space.

1. find O's on edges

2. dfs these edge Os. (traverse left,up,right,down and access all connected Os). mark

the adjacent O with Y

3. traverse the board, mark Os with X--they are surrounded

4. traverse the board, mark Ys with O--they are the ones not surrounded

Glad to not use IDE to debug the code, it passed after correcting some syntax errors.

Thought is right and working! 

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

public class Solution { private void dfsMarking(char[][] board, int x, int y){ if(board[y][x]!='O')return; board[y][x]='Y'; //let it walk left,up,right,down if(x>1){ dfsMarking(board,x-1,y); } if(y>1){ dfsMarking(board,x,y-1); } if(x<board[0].length-1){ dfsMarking(board,x+1,y); } if(y<board.length-1){ dfsMarking(board,x,y+1); } } public void solve(char[][] board) { if(board==null||board.length==0)return; //for each edge, if it is O, build an adjacency list for it. this will use extra memory //method 2:still starting from edge, for each O, mark it as Y in place //parallel edge for(int i=0;i<board[0].length;i++){ if(board[0][i]=='O') dfsMarking(board,i,0); //down if(board[board.length-1][i]=='O') dfsMarking(board,i,board.length-1); } //vertcal board[y][x] for(int i=0;i<board.length;i++){ //left if(board[i][0]=='O') dfsMarking(board,0,i); //right if(board[i][board[0].length-1]=='O') dfsMarking(board,board[0].length-1,i); } for(int i=0;i<board[0].length;i++) for(int j=0;j<board.length;j++){ if(board[j][i]=='O') board[j][i]='X'; } for(int i=0;i<board[0].length;i++) for(int j=0;j<board.length;j++){ if(board[j][i]=='Y') board[j][i]='O'; } } }