General solution of island problems and DFS framework

Reference link :
https://leetcode.cn/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/

See an article on the general solution of island problems , The summary is quite up to standard and easy to understand . On this basis , I further summarize and process , Simultaneous use c++ Code implementation .

1. Of grid problems DFS Traversal methods

What we are familiar with DFS（ Depth-first search ） The problem is usually carried out on the tree or graph structure . And what we're going to talk about today DFS problem , It's in a 「 grid 」 In the structure . The island problem is this kind of grid DFS Typical representative of the problem . The traversal of grid structure is more complex than binary tree , If you don't master certain methods ,DFS Code is easy to write lengthy and complicated .

The grid problem is caused by m * n A grid of small squares , Each small square is considered adjacent to its upper, lower, left and right squares , To do some kind of search on such a grid .
Island problem is a typical grid problem . The number in each grid may be 0 perhaps 1. Let's call the number 0 Think of your grid as an ocean grid , The number is 1 Think of your grid as a land grid , In this way, the adjacent land grids are connected into an island .
Under such a setting , There are various variants of the island problem , Including the number of Islands 、 area 、 Perimeter, etc . But these questions , Basically, it can be used DFS Traversal to solve .

2.DFS The basic structure

The grid structure is slightly more complex than the binary tree structure , It is actually a simplified version of the diagram structure . Write on the grid DFS Traverse , First of all, we need to understand DFS Traversal methods , Then write the analogy on the grid structure DFS Traverse . The binary tree we wrote DFS Traversal is generally like this ：

void traverse(TreeNode root) {
    //  Judge  base case
    if (root == null) {
        return;
    }
    //  Access two adjacent nodes ： Left child node 、 Right child node 
    traverse(root.left);
    traverse(root.right);
}

You can see , Binary tree DFS There are two elements ：「 Access adjacent nodes 」 and 「 Judge base case」.

The first element is access to adjacent nodes . The adjacent nodes of a binary tree are very simple , There are only two left and right child nodes . Binary tree itself is a recursively defined structure ： A binary tree , Its left subtree and right subtree are also a binary tree . So our DFS Traversal only needs to recursively call the left subtree and the right subtree .

The second element is Judge base case. Generally speaking , Binary tree traversal base case yes root == null. Such a conditional judgment actually has two meanings ： One side , This means root The subtree pointed to is empty , There is no need to traverse further . On the other hand , stay root == null Return in time , You can let the back root.left and root.right There will be no null pointer exception in the operation .

For... On the grid DFS, We can refer to the binary tree DFS, Write out the grid DFS The two elements of ：

First , How many adjacent nodes are there in the grid structure ？ The answer is up, down, left and right . For lattice (r, c) Come on （r and c Represent row coordinates and column coordinates respectively ）, The four adjacent grids are (r-1, c)、(r+1, c)、(r, c-1)、(r, c+1). let me put it another way , The grid structure is 「 Quad 」 Of .

secondly , grid DFS Medium base case What is it? ？ From the binary tree base case Corresponding to , It should be that there is no need to continue traversing in the grid 、grid[r][c] An array subscript out of bounds exception will appear , That is, those grids beyond the grid .

This is a little counterintuitive , The coordinates can temporarily exceed the scope of the grid ？ This method I call 「 Pollution before treatment 」—— No matter which grid you are currently in , Take a step in four directions first , If you find that you are out of the grid range, return quickly . This is the same as the traversal method of binary tree , First recursively call , Find out root == null Back again .

therefore , grid DFS The traversal framework code is

void dfs(int[][] grid, int r, int c) {
    //  Judge  base case
    //  If the coordinates  (r, c)  Out of grid , Go straight back to 
    if (!inArea(grid, r, c)) {
        return;
    }
    //  Visit 、 Next 、 Left 、 Four adjacent nodes on the right 
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

//  Judge coordinates  (r, c)  In grid or not 
boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
        	&& 0 <= c && c < grid[0].length;

3. How to avoid repeated traversal

Grid structured DFS And binary tree DFS The biggest difference is , Traversal may encounter traversed nodes . This is because , Grid structure is essentially a 「 chart 」, We can think of each lattice as a node in the graph , Each node has four sides up, down, left and right . When traversing the graph , Naturally, you may encounter repeated traversal nodes .

Now ,DFS May keep 「 Go around in circles 」, Never stop .

How to avoid such repeated traversal ？ The answer is to mark the lattice that has been traversed . Take the island issue as an example , We need all values to be 1 On the land grid DFS Traverse . Every time you walk through a land grid , Just change the value of the grid to 2, So when we meet 2 When , I know this is the traversed lattice . in other words , Each grid may take three values ：

0 —— Ocean grid
1 —— Land grid （ Not traversed ）
2 —— Land grid （ Has traversed ）

We add statements to the framework code to avoid repeated traversal ：

void dfs(int[][] grid, int r, int c) {
    //  Judge  base case
    if (!inArea(grid, r, c)) {
        return;
    }
    //  If this grid is not an island , Go straight back to 
    if (grid[r][c] != 1) {
        return;
    }
    grid[r][c] = 2; //  Mark the grid as 「 Has traversed 」
    
    //  Visit 、 Next 、 Left 、 Four adjacent nodes on the right 
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

//  Judge coordinates  (r, c)  In grid or not 
boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
        	&& 0 <= c && c < grid[0].length;
}

such , We have an island problem 、 And even the general purpose of various grid problems DFS Traversal methods . Here are some examples , In fact, it only needs to be in DFS Traverse the framework with a little modification .

4.leetcode 200 Number of Islands

Here you are ‘1’（ land ） and ‘0’（ water ） A two-dimensional mesh of , Please calculate the number of islands in the grid .
Islands are always surrounded by water , And each island can only be combined by horizontal direction / Or a vertical connection between adjacent lands .
Besides , You can assume that all four sides of the mesh are surrounded by water .

Input ：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
Output ：1

Input ：grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
Output ：3

If you apply the above frame , We can easily think of the following solution
Scan the entire 2D mesh , If a position is 1, Take it as the starting point DFS. It's going on DFS In the process , Every time you search 1, Will be marked as 0, Avoid repeated searches .

#include<iostream>
#include<vector>
using namespace std;

bool inArea(vector<vector<string>> &grid, int r, int c) {
    return r>=0 && r<grid.size() && c>=0 && c<grid[0].size();
}

void dfs(vector<vector<string>> &grid, int r, int c) {
    if (!inArea(grid, r, c))  return;
    if (grid[r][c]=="0") return;
    grid[r][c] = "0";
    dfs(grid, r-1, c);
    dfs(grid, r+1, c);
    dfs(grid, r, c-1);
    dfs(grid, r, c+1);
}

void run() {
    //vector<vector<string>> grid = {
   {"1","1","1","1","0"}, {"1","1","0","1","0"}, 
    //                                {"1","1","0","0","0"}, {"0","0","0","0","0"}};
    vector<vector<string>> grid = {
   {"1","1","0","0","0"}, {"1","1","0","0","0"},
                                    {"0","0","1","0","0"}, {"0","0","0","1","1"}};
    int row = grid.size(), col = grid[0].size();
    int ansnum = 0;
    for(int i=0; i<row; i++) {
        for(int j=0; j<col; j++) {
            if (grid[i][j]=="1") {
                ansnum++;
                dfs(grid, i, j);
            }
        }
    }
    cout<<"ansnum is: "<<ansnum<<endl;
}

int main(int argc, char const *argv[])
{
    run();
    return 0;
}

In the above code ,inArea It is judgement. bad case. If not area In the area , Go straight back to .

if (grid[r][c]==“0”), That means it's not an island , Go straight back to .
grid[r][c] = “0”, Mark the island as traversed , Avoid repeated traversal later .

4. leetcode 695 Max Area of Island

Give you a size of m x n The binary matrix of grid .
Islands It's made up of some neighboring 1 ( Representing land ) A combination of components , there 「 adjacent 」 Ask for two 1 Must be in In four horizontal or vertical directions adjacent . You can assume grid The four edges of are all 0（ Representative water ） Surrounded by a .
The area of the island is the value of 1 Number of cells .
Calculate and return grid The largest island area in . If there were no Islands , Then the return area is 0 .

Example 1：

Input ：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output ：6
explain ： The answer should not be 11 , Because the island can only contain horizontal or vertical 1 .

#include<iostream>
#include<vector>
using namespace std;

bool inArea(vector<vector<int>> &grid, int r, int c) {
    return r>=0 && r<grid.size() && c>=0 && c<grid[0].size();
}

int dfs(vector<vector<int>> &grid, int r, int c) {
    if (!inArea(grid, r, c)) {
        return 0;
    }
    if (grid[r][c] != 1) {
        return 0;
    }
    grid[r][c] = 0;
    return 1 + dfs(grid, r-1, c)+dfs(grid, r+1, c)+dfs(grid, r, c-1)+dfs(grid, r, c+1);
}

void run() {
    vector<vector<int>> grid = {
   {0,0,1,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},
    {0,1,1,0,1,0,0,0,0,0,0,0,0},{0,1,0,0,1,1,0,0,1,0,1,0,0},
    {0,1,0,0,1,1,0,0,1,1,1,0,0},{0,0,0,0,0,0,0,0,0,0,1,0,0},
    {0,0,0,0,0,0,0,1,1,1,0,0,0},{0,0,0,0,0,0,0,1,1,0,0,0,0}};

    int maxarea = 0;
    int row=grid.size(), col=grid[0].size();
    for(int i=0; i<row; i++) {
        for(int j=0; j<col; j++) {
            if (grid[i][j]==1) {
                int curarea = dfs(grid,i,j);
                maxarea = max(curarea, maxarea);
            }
        }
    }
    std::cout<<"maxarea is: "<<maxarea<<endl;
}

int main(int argc, char const *argv[])
{
    run();
    return 0;
}

The only difference from the previous calculation of the number of islands is ,dfs In the process of finding the area , If you encounter 1, The area of the current island is in four directions dfs And add the area 1.

5.LeetCode 463. Island Perimeter

Given a row x col Two dimensional grid map of grid , among ：grid[i][j] = 1 Representing land , grid[i][j] = 0 Water area .
Grid in Grid Horizontal and vertical The directions are connected （ The diagonal directions are not connected ）. The whole grid is completely surrounded by water , But there happens to be an island （ Or say , An island made up of one or more grids representing land ）.
There's No... in the island “ lake ”（“ lake ” And not connected to the water around the island ）. The side length of the grid is 1 The square of . The grid is rectangular , And the width and height are not more than 100 . Calculate the perimeter of the island .

Example 1：

Input ：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output ：16
explain ： Its circumference is the circumference in the picture above 16 A yellow edge

#include<iostream>
#include<vector>
using namespace std;

bool isArea(vector<vector<int>> grid, int r, int c) {
    return r>=0 && r<grid.size() && c>=0 && c<grid[0].size();
}

int dfs(vector<vector<int>> grid, int r, int c) {
    //  Beyond the boundary of the island , Perimeter plus 1
    if (!isArea(grid, r, c)) {
        return 1;
    }
    //  At this time, I came across the sea , Perimeter plus 1
    if (grid[r][c] == 0) {
        return 1;
    }
    if (grid[r][c] != 1) {
        return 0;
    }
    //  Note that the value cannot be assigned to 0
    grid[r][c] = -1;
    return dfs(grid, r-1, c)+dfs(grid, r+1, c)+dfs(grid, r, c-1)+dfs(grid, r, c+1);
}

void run() {
    vector<vector<int>> grid = {
   {0,1,0,0}, {1,1,1,0}, {0,1,0,0}, {1,1,0,0}};
    int result = 0;
    for(int i=0; i<grid.size(); i++) {
        for(int j=0; j<grid[0].size(); j++) {
            if (grid[i][j]==1) {
                result = dfs(grid, i, j);
            }
        }
    }
    cout<<"result is: "<<result<<endl;
}

int main(int argc, char const *argv[])
{
    run();
    return 0;
}

The general idea is the same as above , The only difference , The logic of perimeter calculation , For details, please refer to the notes in the code .