LeetCode: 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

Solution:
这道题本身不难，关键是逆向思维，先从四个边界开始找‘O’, 找到后换成'D', 用一个queue递归扫描所有连通区域，最后凡是没有没有变成D的O都是被X包围的；注意点是二维数组的操作，code如下：

	public class Solution {
	class Element{
	int x;
	int y;
	Element(int x, int y){
	this.x = x;
	this.y = y;
	}
	}
	public void solve(char[][] board) {
	if(board == null||board.length==0) return;
	int row = board.length;
	int col = board[0].length;
	Queue<Element> qu = new LinkedList<Element>();
	for(int i=0; i<row; i++){
	if(board[i][0] == 'O')
	qu.add(new Element(i, 0));
	if(board[i][col-1] == 'O')
	qu.add(new Element(i, col-1));
	}
	for(int i=0; i<col; i++){
	if(board[0][i] == 'O')
	qu.add(new Element(0, i));
	if(board[row-1][i] == 'O')
	qu.add(new Element(row-1, i));
	}
	while(!qu.isEmpty()){
	Element e = qu.remove();
	board[e.x][e.y] = 'd';
	if(e.x>0 && board[e.x-1][e.y]=='O')
	qu.add(new Element(e.x-1, e.y));
	if(e.x<row-1 && board[e.x+1][e.y]=='O')
	qu.add(new Element(e.x+1, e.y));
	if(e.y>0 && board[e.x][e.y-1]=='O')
	qu.add(new Element(e.x, e.y-1));
	if(e.y<col-1 && board[e.x][e.y+1]=='O')
	qu.add(new Element(e.x, e.y+1));
	}
	for(int i=0; i<row; i++)
	for(int j=0; j<col; j++){
	if(board[i][j] == 'O')
	board[i][j]='X';
	if(board[i][j] == 'd')
	board[i][j]='O';
	}
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub