被围绕的区域(dfs)

小咪咪 2022-11-03 11:57 126阅读 0赞

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

## 题目描述 ##

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

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

示例:

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

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

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

解释:

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

## 分析 ##

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

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

在具体处理上dfs或者bfs都可以，向四周遍历时候记得不能出界。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70]

具体代码：

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

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

![image-20201114211553660][]

[Link 1]: https://github.com/javasmall/bigsai-algorithm
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70]: /images/20221024/ce6565199c0548569efa4dedcdba3717.png
[image-20201114211553660]: /images/20221024/b1740c2101ef46e9b744fa02be0a9bd5.png