LeetCode -- Surrounded Regions

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


在由'X'和'O'組成的矩陣中，找出所有被'X'包圍的'O'，將它們替換為'X'。


思路：
1.本題可以DFS也可以BFS，但是DFS速度會慢一些，無法通過測試數據。無論哪種方式，就是從四個邊的'O'作為切入點n（如果BFS，需要先將四個邊的'O'入隊列），遍歷時找到n的上下左右鄰居，分別進行標記（假設標記為A），凡是標記為A的點即為：不能被圍的'O'，以這些鄰居為中心繼續下一次標記。
2.然後對board做一個遍歷，把剩余的'O'賦值為'X'，而'A'賦值為'O'即可。


實現代碼：

public class Solution {
    public void Solve(char[,] board) 
    {
       	var row = board.GetLength(0);
    	var col = board.GetLength(1);
    	
    	if(row < 2 || col < 2){
    		return;
    	}
    	
    	// try go from left & right boundary
    	var q = new Queue();
    	for(var i = 0;i < row; i++){
    		if(board[i , 0] == 'O'){
    			q.Enqueue(new Pos(i , 0));
    		}
    		if(board[i , col - 1] == 'O'){
    			q.Enqueue(new Pos(i , col - 1));
    		}
    	}
    	
    	// try go from top & down boundary
    	for(var i = 0;i < col; i++){
    		if(board[0,i] == 'O'){
    			q.Enqueue(new Pos(0 , i));
    		}
    		if(board[row - 1 , i] == 'O'){
    			q.Enqueue(new Pos(row - 1 , i));
    		}
    	}
    	Bfs(ref board, row, col , q);
    	
    	// restore 'A' to 'O'
    	// mark 'O' to 'X'
    	for(var i = 0;i < row; i++){
    		for(var j = 0;j < col; j++){
    			if(board[i,j] == 'O'){
    				board[i,j] = 'X';
    			}
    			if(board[i,j] == 'A'){
    				board[i,j] = 'O';
    			}
    		}
    	}
    }




private void Bfs(ref char[,] board, int rowLen, int colLen, Queue q)
{
	if(q.Count == 0){
		return;
	}
	
	var q1 = new Queue();
	while(q.Count > 0){
		var p = q.Dequeue();
		board[p.row, p.col] = 'A';
		
		// move up
		if(p.row > 0 && board[p.row - 1, p.col] == 'O'){
			q1.Enqueue(new Pos(p.row - 1, p.col));	
		}
		// move down
		if(p.row < rowLen - 1 && board[p.row + 1, p.col] == 'O'){
			q1.Enqueue(new Pos(p.row + 1, p.col));
		}
		// move right
		if(p.col < colLen - 1 && board[p.row, p.col + 1] == 'O'){
			q1.Enqueue(new Pos(p.row, p.col + 1));
		}
		// move left
		if(p.col > 0 && board[p.row, p.col - 1] == 'O'){
			q1.Enqueue(new Pos(p.row, p.col - 1));
		}
	}
	
	Bfs(ref board, rowLen, colLen, q1);
}


class Pos{
	public Pos(int r, int c){
		row = r;
		col = c;
	}
	
	public int row;
	public int col;
}


}