Algorithms · One Question of the Day (Detailed + Multiple Solutions) — day13

Hits: 0

[Battle against [the Blue Bridge Cup] ] Algorithm · One Question of the Day (Detailed + Multiple Solutions) — day13

✨Blogger introduction

[💂 Personal homepage: Suzhou Program Dabai]

[💂 Personal community: CSDN programmers all over the country]

🤟Introduction to the author: Member of China DBA Alliance (ACDU), administrator of CSDN programmers (women) gathering places across the country. Currently engaged in the development of industrial automation software. Good at C#, Java, machine vision, underlying algorithms and other languages. Qiyue Software Studio will be established in 2019, and Suzhou Kaijie Intelligent Technology Co., Ltd. will be registered in 2021

💅 If you have any questions, please send a private message, we will reply in time

👤 WeChat account: stbsl6, WeChat public account: Suzhou Program Dabai

💬If the article is helpful to you, welcome to follow, like, and favorite (one-click three links)

🎯 If you want to join the technical exchange group, you can add me as a friend, and the group will share learning materials

General solution to island problems, [DFS] traversal framework

In LeetCode, the “island problem” is a series of problems, such as:

The DFS (depth-first search) problem we are familiar with is usually carried out on a tree or graph structure. And the DFS problem we are going to discuss today is carried out in a ” [grid] problem we are familiar with is usually carried out on a tree or graph structure. And the DFS problem we are going to discuss today is carried out in a ” [grid] ” structure. The island problem is a typical example of this type of grid DFS problem. The grid structure is more complicated to traverse than the binary tree. If you don’t master a certain method, the DFS code is easy to write tedious and complicated.

This article will take the island problem as an example to show the general idea of ​​DFS for grid problems and how to make the code concise.

[DFS traversal] method for grid problems

Basic Concepts of Grid Problems

First of all, it is clear how the grid structure in the island problem is defined to facilitate our later discussion.

The grid problem is a grid composed of m × nsmall squares, and each small square is considered to be adjacent to its four squares.

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

Basic structure of DFS

The grid structure is slightly more complicated than the binary tree structure, it is actually a simplified version of the graph structure. To write the DFS traversal on the grid, we must first understand the DFS traversal method on the binary tree, and then write the DFS traversal on the grid structure by analogy. The binary tree DFS traversal we write is generally like this:

void  traverse ( TreeNode root ) {
     // invalid base case 
    if ( root == null ) {
         return ;
    }
    // visit two adjacent nodes: left child node, right child node
    traverse(root.left);
    traverse(root.right);
}

It can be seen that the DFS of the binary tree has two elements: “visiting adjacent nodes” and “judging base case”.

The first element is to visit adjacent nodes. The adjacent nodes of a binary tree are very simple, with only two left and right children. A binary tree itself is a recursively defined structure: a binary tree whose left and right subtrees are also a binary tree. Then our DFS traversal only needs to recursively call the left subtree and the right subtree.

The second element is judgment base case. In general, the base case for binary tree traversal is root == null. Such a conditional judgment actually has two meanings: on the one hand, it means that the subtree pointed to by the root is empty, and there is no need to traverse further down. On the other hand, returning in time at root == null the time can prevent the following root.left and root.right operations from having a null pointer exception.

For the DFS on the grid, we can refer to the DFS of the binary tree and write out the two elements of the grid DFS:

First, how many adjacent nodes do cells in the grid structure have? The answer is four up, down, left and right. For lattice (r, c) (r and c represent row and column coordinates, respectively), the four adjacent lattices are respectively (r - 1, c)、(r + 1, c)、(r, c - 1)、(r, c + 1). In other words, the grid structure is “quadrant”.

Second, what is the base case in grid DFS? From the base casecorrespondence , it should be the grid that does not need to continue to traverse, and grid[r][c]the array subscript out-of-bounds exception will occur, that is, those grids that exceed the grid range.

This is a little counter-intuitive, the coordinates can temporarily go beyond the grid? I call this method “pollution first and then treatment” — no matter which grid it is currently in, take a step in four directions, and then return quickly if you find that you have stepped out of the grid range. This is the same as the traversal method of the binary tree, first recursively call, find root == nulland then return.

In this way, we get the skeleton code for grid DFS traversal:

void  dfs ( int [][] grid, int r, int c)  {
     // Judgment base case 
    // If the coordinates (r, c) are beyond the grid range, return 
    if (!inArea(grid, r, c) ) {
         return ;
    }
    // Access four adjacent nodes up, down, left and right 
    dfs(grid, r - 1 , c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

// Determine if the coordinates (r, c) are in the grid 
boolean  inArea ( int [][] grid, int r, int c)  {
     return  0 <= r && r < grid.length
            && 0 <= c && c < grid[0].length;
}

How to avoid double traversal

The biggest difference between the DFS of the grid structure and the DFS of the binary tree is that the traversed nodes may be encountered during the traversal. This is because the grid structure is essentially a “graph”, and we can regard each grid as a node in the graph, and each node has four edges up, down, left, and right. When traversing the graph, it is natural to encounter repeated traversal nodes.

At this time, DFS may keep “circling in circles” and never stop, as shown in the following figure:
How to avoid such repeated traversal? The answer is to mark cells that have already been traversed. Taking the island problem as an example, we need to do a DFS traversal on all land cells with a value of 1. Every time we walk through a land grid, change the value of the grid to 2, so that when we encounter 2, we know that this is the traversed grid. That is, each cell may take on three values:

  • 0 – ocean grid

  • 1 – land grid (not traversed)

  • 2 – land grid (traversed)

We add statements to avoid repeated traversal in the framework code:

void dfs(int[][] grid, int r, int c) {
    if (!inArea(grid, r, c)) {
        return;
    }
    // If the grid is not an island, return directly 
    if (grid[r][c] != 1 ) {
         return ;
    }
    grid[r][c] = 2 ; // mark the grid as "traversed"

    // Access four adjacent nodes up, down, left and right 
    dfs(grid, r - 1 , c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

// Determine if the coordinates (r, c) are in the grid 
boolean  inArea ( int [][] grid, int r, int c)  {
     return  0 <= r && r < grid.length
            && 0 <= c && c < grid[0].length;
}

In this way, we have a general DFS traversal method for island problems, and even various grid problems. The few examples mentioned below actually only need to be modified slightly on the DFS traversal framework.

Notice:
In some solutions, the "traversed land grid" may be marked as 0 as the ocean grid, euphemistically called "land sinking method",
That is, after traversing a land grid, let the land "sink" into the ocean. This method seems very clever, but in fact it has a lot of hidden dangers.
Because then we cannot distinguish between "ocean lattices" and "traversed land lattices". If the subject is a little more complicated, this is prone to bugs.

solution to the island problem

After understanding the DFS traversal method of the grid structure, the island problem is not difficult to solve. Let’s take a look at how the three problems can be solved by DFS traversal.

the largest area of ​​the island

LeetCode 695. Max Area of Island (Medium)

Given a non-empty two-dimensional array grid containing some 0s and 1s, an island is a set of adjacent 1s (representing land), where “adjacent” requires that the two 1s must be horizontal or vertical. adjacent. You can assume that all four edges of the grid are surrounded by 0s (for ocean).
Find the largest island area in the given 2D array. If there are no islands, the area is returned as 0.

This problem only needs to do DFS traversal of each island to find the area of ​​each island. The method of finding the area of ​​the island is also very simple. The code is as follows. Each time a grid is traversed, the area is increased by one.

int area(int[][] grid, int r, int c) {
    return 1
        + area(grid, r - 1, c)
        + area(grid, r + 1, c)
        + area(grid, r, c - 1)
        + area(grid, r, c + 1);
}

The complete problem solving code is as follows:

public int maxAreaOfIsland(int[][] grid) {
    int res = 0;
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == 1) {
                int a = area(grid, r, c);
                res = Math.max(res, a);
            }
        }
    }
    return res;
}

int area(int[][] grid, int r, int c) {
    if (!inArea(grid, r, c)) {
        return 0;
    }
    if (grid[r][c] != 1) {
        return 0;
    }
    grid[r][c] = 2;

    return 1
        + area(grid, r - 1, c)
        + area(grid, r + 1, c)
        + area(grid, r, c - 1)
        + area(grid, r, c + 1);
}

boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length
            && 0 <= c && c < grid[0].length;
}

land reclamation problem

LeetCode 827. Making A Large Island (Hard)

On a 2D map, where 0 represents ocean and 1 represents land, we can only turn at most one grid of 0 (ocean) into 1 (land). After reclamation, what is the size of the largest island on the map?

This question is an upgraded version of the question about the largest area of ​​an island. Now we have the ability to reclaim the land, and we can turn an ocean grid into a land grid, and then connect two islands together. So after reclamation, what is the largest possible island size?

The general idea is not difficult to think of, we first calculate the area of ​​all the islands, and mark the area of ​​the islands on all the grids. Then search which ocean lattice has the largest area of ​​two adjacent islands. For example, the ocean grid in the red box in the figure below is adjacent to the island on the top and the left. We can calculate that the area of ​​the islands that can be connected after it becomes land is 7 + 1 + 2 = 10.

However, this approach may encounter a problem. As shown in the ocean grid in the red box in the figure below, its top and left sides are adjacent to islands. At this time, is the area of ​​the connected islands 7 + 1 + 7? Obviously not. The two 7s come from the same island, so the island area obtained after reclamation should only be 7 + 1 = 8.
As you can see, for the algorithm to be correct, we need to be able to distinguish whether two adjacent 7s in an ocean grid are from the same island. Then, instead of marking the area of ​​the island in the square, we should mark the index (subscript) of the island, and use an array to record the area of ​​each island, as shown in the figure below. This way we can find the ocean grid in the red box, whose “two” adjacent islands are actually the same.

It can be seen that this question actually does two DFS passes on the grid: the first DFS traverses the land grid, calculates the area of ​​each island and marks the island; the second DFS traverses the ocean grid and observes each ocean grid Adjacent land cells.

The basic idea of ​​​​this question is like this. The specific code has some details that need to be paid attention to, but it has little connection with the theme of this article. You can think for yourself how to translate the above ideas into code.

perimeter of the island

LeetCode 463. Island Perimeter (Easy)

Given a 2D grid map containing 0s and 1s, where 1 is land and 0 is ocean. The cells in the grid are connected horizontally and vertically (not diagonally). The entire grid is completely surrounded by water, but has exactly one island in it (one or more grids representing land are connected to form an island).

There are no “lakes” in the islands (a “lake” means the body of water is inside the island and not connected to the water around the island). A lattice is a square with side length 1. Calculate the perimeter of the island.

To be honest, using DFS to solve this problem is not the optimal method. For islands, it is easier to find the perimeter directly mathematically. However, this question is a good example to understand the DFS traversal process. If you don’t believe me, follow me to see it.

Review the basic framework of grid DFS traversal:

void dfs(int[][] grid, int r, int c) {
    if (!inArea(grid, r, c)) {
        return;
    }
    // If the grid is not an island, return directly 
    if (grid[r][c] != 1 ) {
         return ;
    }
    grid[r][c] = 2 ; // mark the grid as "traversed"

    // Access four adjacent nodes up, down, left and right 
    dfs(grid, r - 1 , c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

// Determine if the coordinates (r, c) are in the grid 
boolean  inArea ( int [][] grid, int r, int c)  {
     return  0 <= r && r < grid.length
            && 0 <= c && c < grid[0].length;
}

!inArea(grid, r, c), that is, the coordinates are (r, c) beyond the range of the grid, which is what I call “pollution first and then treatment”

grid[r][c] != 1, that is, the current grid is not an island grid, which is divided into two cases:

grid[r][c] == 0, the current grid is the ocean grid

grid[r][c] == 2, the current grid is the traversed land grid

So what does this have to do with the perimeter of our islands? In fact, the perimeter of the island is the calculation of all the “edges” of the island, and these edges are dfsthe positions returned by the function in our DFS traversal. Looking at the example question, we can divide the edges in the perimeter of the island into two categories, as shown in the following figure. The yellow edge is the perimeter adjacent to the grid boundary, while the blue edge is the perimeter adjacent to the ocean lattice.

When our dfsfunction returns because “coordinates are (r, c)out of grid range”, it actually passes a yellow edge; and when the function returns because “the current grid is an ocean grid”, it actually passes through a blue edge side. In this way, we associate the perimeter of the island with the DFS traversal , and our problem solving code is ready to come out:

public  int  islandPerimeter ( int [][] grid)  {
     for ( int r = 0 ; r < grid.length; r++) {
         for ( int c = 0 ; c < grid[ 0 ].length; c++) {
             if (grid [r][c] == 1 ) {
                 // The problem is limited to only one island, just calculate one and 
                return dfs(grid, r, c);
            }
        }
    }
    return 0;
}

int  dfs ( int [][] grid, int r, int c)  {
     // The function returns because "coordinates (r, c) are out of grid range", corresponding to a yellow edge 
    if (!inArea(grid, r, c )) {
         return  1 ;
    }
    // The function returns because "the current grid is an ocean grid", corresponding to a blue edge 
    if (grid[r][c] == 0 ) {
         return  1 ;
    }
    // The function returns because "the current grid is a traversed land grid", it has nothing to do with the perimeter 
    if (grid[r][c] != 1 ) {
         return  0 ;
    }
    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);
}

// Determine if the coordinates (r, c) are in the grid 
boolean  inArea ( int [][] grid, int r, int c)  {
     return  0 <= r && r < grid.length
            && 0 <= c && c < grid[0].length;
}

💫Click on the direct data to receive💫

❤️Follow Suzhou program Dabai public account ❤️

👇 👇👇

You may also like...

Leave a Reply

Your email address will not be published.