[leetcode]Surrounded Regions

dfs过得太蹊跷了，本博文算法作废，新博文地址：[leetcode]Surrounded Regions

 

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

 有点像围棋——一旦把你全部围住，就把你的棋子全部变成我的。

刚开始看这道题的时候，考虑的过于简单了：先遍历整个棋盘，遇到O则上下左右找X，如果四个方向都找到了X，则表示该O可以被替换。这显然是不对的。

比如：

{ 'O','X','X','O','X'},
{ 'X','O','O','X','O'},
{ 'X','O','X','O','X'},
{ 'O','X','O','O','O'},
{ 'X','X','O','X','O'}

 红圈圈上下左右都能找到X，但是还是可以沿着黄色的路径突围，因为我将这道题解释为escape 或者 find the way out。首先定义什么情况下才能escape或者find  a way out：找到一条出路，可以走到棋盘的边界。

比如上图中黄色这条路。

因此我第二种做法是对于矩阵中的每一个O，用DFS看其是否能找到一个出路。 后来发现，比如上面的矩阵，当找不到出路时候，回溯比较麻烦，而且当矩阵比较大的时候，做的无用功可能太多了，可能导致超时。

因此我的第三种做法是先确定每一个可能的出口，然后根据出口找出路上的节点。

1.即先找到边界上的O点，如果矩阵中escap的棋子，必须经过这些O点才能escape。

2.从边界上的O点进行DFS，找到所有escapde的棋子。将escape的点做出标记。

3.然后再次遍历矩阵，对那些未作出标记的O点，设置为X即可。

代码如下

public void solve(char[][] board) {
		if (board == null || board.length == 0) {
			return;
		}
		int height = board.length;
		int width = board[0].length;
		boolean[][] visit = new boolean[height][width]; 
		for(int i = 0 ; i < width; i++){
			if(board[0][i] == 'O')	visit[0][i] = true;
			if(board[height - 1][i] == 'O') visit[height - 1][i] = true;
		}
		for(int i = 0 ; i < height; i++){
			if(board[i][0] == 'O') visit[i][0] = true;
			if(board[i][width - 1] == 'O') visit[i][width - 1] = true;
		}
		for(int i = 0 ; i < visit.length; i++){
			for(int j = 0; j < visit[0].length;j++){
				if(visit[i][j]){
					dfs(board, visit, i, j);
				}
			}
		}
		for(int i = 1; i < height; i++){
			for(int j = 1; j < width; j++){
				if(board[i][j] == 'O' && !visit[i][j]){
					board[i][j] = 'X';
				}
			}
		}
	}
	private void dfs(char[][] board,boolean[][] visit,int i ,int j){
		visit[i][j] = true;
		if(i > 0 && board[i - 1][j] == 'O' && !visit[i - 1][j]){
			dfs(board, visit, i - 1, j);
		}
		if(i < visit.length - 1 && board[i + 1][j] == 'O' && !visit[i + 1][j]){
			dfs(board, visit, i + 1, j);
		}
		if(j > 0 && board[i][j - 1] == 'O' && !visit[i][j - 1]){
			dfs(board, visit, i, j - 1);
		}
		if(j < visit[0].length - 1 && board[i][j + 1] == 'O' && !visit[i][j + 1]){
			dfs(board, visit, i, j + 1);
		}
	}