DFS is a general solution for island grid problems

The DFS problems that we’re familiar with are usually done on trees or graphs, and the new DFS are done on grids, like the island problem,

First, the basic concept of grid problem

The grid problem is a network of m* N small squares, each of which is adjacent to its top, bottom, left and right squares, on which some kind of search is to be performed. = =

Island problem is a kind of typical grid problem. The number in each grid may be 0 or 1. We regard the grid with the number 0 as ocean grid, and the grid with the number 1 as land grid, so that the adjacent land grids are connected to form an island.

The basic structure of DFS

1. Binary tree DFS traversal method

The grid problem is a little more complicated than binary tree structure, which is actually a simplified graph structure. To write a good DFS traversal on a grid, first understand the binary tree DFS traversal method.

void treeTraverse(TreeNode root){
	// Base case
	if(root==null) return;
	// Access adjacent nodes: left child, right child
    treeTraverse(root.left);
    treeTraverse(root.right);    
}
Copy the code

As can be seen, the DFS of binary trees has two elements:

Accessing adjacent nodes

The adjacent nodes of a binary tree are very simple, with only two left and right child nodes. The binary tree itself is a recursively defined structure: a binary tree, its left and right subtrees are themselves a binary tree, our DFS traversal only need to recursively call the left and right subtrees.

Judge basecase

In general, the base case for binary tree traversal is root == NULL. Root. Left and root. Right operations do not have null pointer exceptions.

2. DFS on the grid — refer to binary tree DFS

The adjacent nodes of a cell on a grid

There are four adjacent nodes up and down; For the grid (r, c), four neighbouring grid (r – 1, c), (r + 1, c), (r, c – 1), (r, c + 1); The network structure is quadrilateral

Base case in grid DFS

Grid [r][C] will show the out-of-bounds exception of array subscript, that is, those cells beyond the range of the grid

Understand that coordinates can be temporarily out of the grid:

“Pollute first, clean up later” – take one step in each of the four directions, regardless of which cell you are in. If you find yourself out of the grid, go back. This is the same as binary tree traversal method, first recursively called, found root==null return.

Thus, we get the “frame code” for the grid DFS traversal == :

/* *gird grid two-dimensional matrix array * r, c currently processing grid horizontal and vertical */
void dfs(char[][] grid,int r,int c){
	// Base case, if the coordinates are outside the grid range, return out of bounds
	if(r<0||r>grid.length||c<0||c>grid[0].length) return;
	
	// Access the top, bottom, left, right, and four adjacent nodes
	dfs(grid,r-1,c);
	dfs(grid,r+1,c);
	dfs(grid,r,c-1);
	dfs(gird,r,c+1);
}
Copy the code

3. How to avoid repeated traversal

The biggest difference between grid structure DFS and binary tree DFS is that traversal nodes can be encountered. This is because the grid structure is essentially a graph, and we can think of each node as a node in the graph, with four sides facing “up, down, left, and right”. As you traverse the graph, it is natural to encounter nodes that are repeatedly traversed. The DFS will go in circles and never stop, as shown below

How do I avoid repeated traversal — == marks already traversed cells ==

In the case of the island problem, we need to traverse the left DFS on all the land cells with a value of 1, setting the value to 2 for each land cell we pass, so that when we encounter a 2, we know it is a traversed cell. That is, each cell may take three values:

0 — Ocean grid

1 — Land grid (not traversed)

2 — Land grid (traversed)

★★★★ We put a statement in the framework code to avoid repeated traversal

void dfs(char[][] grid,int r,int c){
	//1. Determine the base case, if the coordinates are outside the grid range, out of bounds return
	if(r<0||r>grid.length||c<0||c>grid[0].length) return;
	
	//【 new 】2. If the grid is not an island, it is an ocean or an island already visited, return
    if(grid[r][c]! ='1') return;
    
	// [S] 3. It is an unvisited island
    grid[r][c]='2';// Mark as already accessed
    
	// Access the top, bottom, left, right, and four adjacent nodes
	dfs(grid,r-1,c);
	dfs(grid,r+1,c);
	dfs(grid,r,c-1);
	dfs(gird,r,c+1);	
}
Copy the code

Thus, we arrive at a universal DFS traversal for island problems, and for grid problems of all kinds.

** Tip: ** In some solutions, the “traversed land grid” may be marked as 0, which is the same as the word for ocean, and is called the “land submerging method”. But this is not good, can not distinguish between “ocean grid” and “traversed land grid”, if the problem is more complex, easy to bug.

Third, sample

1. Number of islands

class Solution {
    public int numIslands(char[][] grid) {
        if(grid==null||grid.length==0) return 0;

        int num_islands=0;
        for(int r=0; r<grid.length; r++){for(int c=0; c<grid[0].length; c++){if(grid[r][c]! ='1') continue;// [key] skip the backtrace if the traversal is not suitable
                
                ++num_islands;// [key] the appropriate node appears, as long as there is a 1, there is an island, and this island has at least one land; DFS marks all of its landdfs(grid,r,c); }}return num_islands;
    }
    
    public void dfs(char[][] grid,int r,int c){
        //1. Judge base case: not in the grid, return out of bounds
        if(r<0||r>=grid.length||c<0||c>=grid[0].length) return;
        //2. If the grid is not an island, but an ocean or already visited island, go back
        if(grid[r][c]! ='1') return;

        //3. It is an unvisited island
        grid[r][c]='2';// Mark as already accessed

        // Access the top, bottom, left and right adjacent nodes recursively
        dfs(grid,r-1,c);
        dfs(grid,r+1,c);
        dfs(grid,r,c-1);
        dfs(grid,r,c+1); }}Copy the code

2. The area of the largest island

The size of the largest island of all

1. When doing DFS for each island, find the area of each island. 2. Finding the area of an island is also simple -- for each land cell you traverse, add the area by one */
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int maxnum=0;
        for(int r=0; r<grid.length; r++){for(int c=0; c<grid[0].length; c++){// Skip the backtrace for ocean nodes or visited nodes
                if(grid[r][c]! =1) continue;
                // Valid node DFS, where a DFS can find a piece of land, calculate the area of a piece of land
                intcurnum=dfs(grid,r,c); maxnum=maxnum>curnum? maxnum:curnum; }}return maxnum;
    }
    // Each layer DFS returns the number of nodes within the current layer
    public int dfs(int[][] grid,int r,int c){
        // Basecase returns out of bounds
        if(r<0||r>=grid.length||c<0||c>=grid[0].length) return 0;

        // Invalid node returns, ocean may have been visited
        if(grid[r][c]! =1) return 0;

        // Active node, which processes the current node and adjacent nodes of DFS
        grid[r][c]=2;
        return 1                            // [key] Return the number of valid nodes including the current layer node and DFS
                +dfs(grid,r-1,c)
                +dfs(grid,r+1,c)
                +dfs(grid,r,c-1)
                +dfs(grid,r,c+1); }}Copy the code

3. The maximum area connected to reclaimed islands

Easy wrong:

/* 1. DFS finds the islands, numbers each island, and fills in the island number for each land cell of the island on the Mark array. 2. When an island is traversed, map is used to record the size of the islands. 3. The 2d array traverses to find ocean nodes and check whether the upper and lower nodes of each ocean node belong to islands with different numbers. If so, fill in the ocean node and the surrounding islands can be connected to form one large island. 【 错 误 】 1. It is not necessary to connect two islands, but it can be multiple islands. Note that the top, bottom, left and right may be different land grids on the same island, and the island can only be counted once
class Solution {
    public int largestIsland(int[][] grid) {
        //1. Find each island, mark the array to mark the same island
        int[][] mark=new int[grid.length][grid[0].length];// Initialize the tag array to 0
        // Map stores the size of each island
        Map<Integer,Integer> map=new HashMap<>();

        Record the area of the largest island
        int maxsum=0;
        //2. Traverse, each island block is marked and counted
        int sign=3;// Mark the number of the array
        for(int r=0; r<grid.length; r++){for(int c=0; c<grid[0].length; c++){if(grid[r][c]! =1) continue;
                
                int curnum=dfs(grid,r,c,mark,sign);// Complete the marking and counting of an island blockmap.put(sign,curnum); sign++; maxsum=Math.max(maxsum,curnum); }}// If there are no islands, fill in an ocean grid
        if(maxsum==0) return 1;
        If there are islands, iterate through the Mark array and calculate the maximum number of adjacent nodes for each ocean node
        for(int r=0; r<mark.length; r++){for(int c=0; c<mark[0].length; c++){// Not ocean node skipped
                if(mark[r][c]! =0) continue;
                //★★★【 key 】 Ocean node, use a set to select the adjacent nodes of ocean node (here set stores the island number, the land cell number of the same island is consistent, the land cell number of different islands is different
                Set<Integer> set=getNeighborsSign(mark,r,c);
                if(set.size()<1) continue;// The ocean grid has no land grid adjacent to it
                int cursum=1;
                for(int neighborSign:set){
                    cursum+=map.get(neighborSign);// Select the size of the islands with corresponding numbers from the map} maxsum=Math.max(maxsum,cursum); }}return maxsum;
    }
    // Count the number of land grids in the current layer and DFS for each island, and mark the island
    public int dfs(int[][] grid,int r,int c,int[][] mark,int sign){
        if(r<0||r>=grid.length||c<0||c>=grid[0].length) return 0;

        // Invalid node returns, ocean may have been visited
        if(grid[r][c]! =1) return 0;

        // Active node, which processes the current node and adjacent nodes of DFS
        grid[r][c]=2;
        mark[r][c]=sign;//★★【 key 】 island block mark
        
        return 1                            
                +dfs(grid,r-1,c,mark,sign)
                +dfs(grid,r+1,c,mark,sign)
                +dfs(grid,r,c-1,mark,sign)
                +dfs(grid,r,c+1,mark,sign);  
    }

    //★★ Find the island number of the adjacent nodes of each ocean node
    public Set<Integer> getNeighborsSign(int[][] mark,int r,int c){
        Set<Integer> set=new HashSet<>();
        // Adjacent nodes must be in mark, and the island node mark[r][c]! = 0; The up and down or so
        if(r-1> =0&&mark[r-1][c]! =0) set.add(mark[r-1][c]);
        if(r+1<mark.length&&mark[r+1][c]! =0) set.add(mark[r+1][c]);
        if(c-1> =0&&mark[r][c-1]! =0) set.add(mark[r][c-1]);
        if(c+1<mark.length&&mark[r][c+1]! =0) set.add(mark[r][c+1]);

        returnset; }}Copy the code

4. Perimeter of the island

Grid DFS traversal basic framework, DFS function directly returns the case

Case one: the node is out of bounds and beyond the gridif(r<0||r>=grid.length||c<0||c>=grid[0].length) return 0; Grid [r][C]! =1Grid [r][c]==0②grid[r][C]==2, the land cell traversed by the current cellCopy the code

The perimeter of the island is the total edge of the island, and these edges are the positions returned by the DFS function in the DFS traversal

We classify the edges in the perimeter of islands into two categories:

The yellow edge is the perimeter edge adjacent to the grid boundary

The blue edge is the perimeter edge adjacent to the ocean grid

Algorithm idea:

Our DFS function actually experiences a yellow edge when it returns == because the grid coordinates are out of bounds;

When the DFS function returns because the current cell is ocean cell ==, it actually passes through a blue edge.

At this point we associate the edge == of the circumference of the == island with the == DFS traversal ==

/* Method 1 grid DFS + backtrace */
class Solution {
    public int islandPerimeter(int[][] grid) {
        for(int r=0; r<grid.length; r++){for(int c=0; c<grid[0].length; c++){// The previous ocean node processing
                if(grid[r][c]==0) continue;
                // The first valid land node traverses the island block; I'm limited to one island, so I'll just go back
                returndfs(grid,r,c); }}return 0;
    }

    public int dfs(int[][] grid,int r,int c){
        // [key] 1. When the access node is out of bounds, it represents a case of encountering an edge
        if(r<0||r>=grid.length||c<0||c>=grid[0].length) return 1;

        // Invalid node: ocean node, traversed node
        // [key] 2. When the access node is ocean grid, it represents a case where an edge is encountered
        if(grid[r][c]==0) return 1;
        // The node that was traversed when the node was accessed
        if(grid[r][c]==2) return 0;

        // Untraversed node processing
        grid[r][c]=2;
        return dfs(grid,r-1,c)
                +dfs(grid,r+1,c)
                +dfs(grid,r,c-1)
                +dfs(grid,r,c+1); }}/* Method 2: Iterate over each edge of a land grid only if the edge is: 1. 2. Another adjacent grid is ocean grid algorithm: traverse each land grid to see if its four directions are boundary or ocean grid, if so, ret++ */
class Solution {
    public int islandPerimeter(int[][] grid) {
        // Coordinate transform array
        int[] dx={-1.1.0.0};
        int[] dy={0.0, -1.1};

        int cnt=0;
        for(int r=0; r<grid.length; r++){for(int c=0; c<grid[0].length; c++){// Ocean node skipped
                if(grid[r][c]==0) continue;
                // Land grid nodes, traversing adjacent nodes
                for(int k=0; k<dx.length; k++){int tx=r+dx[k];
                    int ty=c+dy[k];
                    //【 key 】 the node is out of bounds; Marine node
                    if(tx<0||tx>=grid.length||ty<0||ty>=grid[0].length||grid[tx][ty]==0) cnt++; }}}returncnt; }}Copy the code

Four, access adjacent nodes, coordinate transformation array +for loop processing

static int[] dx={-1.1.0.0};
statci int[] dy={0.0, -1.1};

for(int k=0; k<4; k++){int tx=c+dx[k];
    int ty=r+dy[k];
    dfs(grid,tx,ty);
}
Copy the code

DFS is a general solution for island grid problems

DFS is a general solution for island grid problems

First, the basic concept of grid problem

The basic structure of DFS

1. Binary tree DFS traversal method

2. DFS on the grid — refer to binary tree DFS

3. How to avoid repeated traversal

Third, sample

1. Number of islands

2. The area of the largest island

3. The maximum area connected to reclaimed islands

4. Perimeter of the island

Four, access adjacent nodes, coordinate transformation array +for loop processing

Related Posts

Springboot2 uses the triple realm of dubbo

Go impulse entry (three) the first taste of IO input and output

SSM Framework — Detailed integration tutorial (Spring+SpringMVC+MyBatis)