被围绕的区域(dfs)

原创公众号：bigsai 欢迎加入力扣打卡
文章已收录在 全网都在关注的数据结构与算法学习仓库 欢迎star

题目描述

给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。

找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例:

X X X X
X O O X
X X O X
X O X X

  

 

  
1
  
2
  
3
  
4
 

运行你的函数后，矩阵变为：

X X X X
X X X X
X X X X
X O X X

  

 

  
1
  
2
  
3
  
4
 

解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

分析

对于题意是很容易理解的，也就是只有和边缘连接的O不会被 X 包围，其他都会被X包围。

这是一道图论搜索题，核心的处理思路就是找矩阵所有边缘开始，如果是x那么跳过，如果是o那么开始查找与该点上下左右联通的点进行标记(被标记则证明没有被包围)。那么最终剩下没有被标记的节点就是保留o。其他节点全部变成x.

在具体处理上dfs或者bfs都可以，向四周遍历时候记得不能出界。

具体代码：

class Solution { int X[]={0,1,0,-1};
	int Y[]={1,0,-1,0};
	public void solve(char[][] board) { int lenx=board.length,leny=board[0].length;
		boolean jud[][]=new boolean[lenx][leny];
		for(int i=0;i<lenx;i++)//两个竖得
		{ if(board[i][0]=='O'&&!jud[i][0]) { judgle(i,0,board,jud); jud[i][0]=true; } if(board[i][leny-1]=='O'&&!jud[i][leny-1]) { judgle(i,leny-1,board,jud); jud[i][leny-1]=true; }
		}
		for(int i=0;i<leny;i++)//两个横得
		{ if(board[0][i]=='O'&&!jud[0][i]) { judgle(0,i,board,jud); jud[0][i]=true; } if(board[lenx-1][i]=='O'&&!jud[lenx-1][i]) { judgle(lenx-1,i,board,jud); jud[lenx-1][i]=true; }
		}
		for(int i=0;i<lenx;i++)
		{ for(int j=0;j<leny;j++) { if(!jud[i][j]) { board[i][j]='X'; } } } }

	private void judgle(int x, int y, char[][] board, boolean[][] jud) {
		// TODO Auto-generated method stub
		for(int i=0;i<4;i++)
		{ int x1=x+X[i]; int y1=y+Y[i]; if(x1>=0&&x1<board.length&&y1>=0&&y1<board[0].length) { if(!jud[x1][y1]&&board[x1][y1]=='O') { jud[x1][y1]=true; judgle(x1, y1, board, jud); } }
		}	
	}
}

  

 

  
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
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
 

咱们下次再见！关注后欢迎加入力扣打卡群(备注力扣 csdn即可)。

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/114230222