`
huntfor
  • 浏览: 201674 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[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);
		}
	}

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics