当前位置:网站首页>Surrounded area (DFS)

Surrounded area (DFS)

2021-03-30 05:25:07 Big sai

Original official account :bigsai Welcome to punch in
The article has been included in Data structure and algorithm learning warehouse that the whole network is paying attention to welcome star

Title Description

Given a two-dimensional matrix , contain ‘X’ and ‘O’( Letter O).

Find all the victims ‘X’ The surrounding area , And put all of these areas ‘O’ use ‘X’ fill .

Example :

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

After running your function , The matrix becomes :

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

explain :

The surrounding area does not exist on the boundary , let me put it another way , On any boundary ‘O’ Will not be filled with ‘X’. Anything not on the border , Or not with the boundary ‘O’ Connected ‘O’ It will be filled with ‘X’. If two elements are adjacent horizontally or vertically , They are “ Connected to a ” Of .

analysis

It's easy to understand the meaning of the title , That is, only those connected to the edge O It won't be X Surround , Everything else will be X Surround .

This is a graph theory search question , The core idea is to find all the edges of the matrix , If it is x So skip , If it is o Then start to find the points connected with the point up, down, left and right for marking ( Being marked proves not to be surrounded ). Then the remaining nodes that are not marked are reserved o. All other nodes become x.

In terms of specific treatment dfs perhaps bfs Fine , You can't go out when you walk around .
 Insert picture description here

Specific code :

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++)// The two stand upright 
		{
    
			
			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++)// The two are horizontal 
		{
    
			
			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);
				}
			}
		}	
	}
}

See you next time ! After paying attention, welcome to join the power button punch out group ( Note force button csdn that will do ).

image-20201114211553660

版权声明
本文为[Big sai]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/03/20210324094710386B.html

随机推荐