Maximum artificial island [how to make all nodes of a connected component record the total number of nodes? + number the connected component]

Preface

How to find the total number of all nodes of connected components ？dfs+visited
How to record the total number of nodes of the connected component for all nodes of the connected component ？ Change the variable to an array ( We use a heap address )
How to determine whether the nodes around a node are two different connected components ？ Number the connected components or Union checking set findFather

One 、 The largest artificial island

Two 、DFS+ Search variant

package everyday.hard;

import java.util.HashSet;
import java.util.Set;

//  The largest artificial island .
public class LargestIsland {
    
    /* target： Only one grid can be removed from 0 Turn into 1, Look at the largest island area .  intuitive ：DFS Find island area ,  How to draw inferences from one instance ？ Since only one 0 Turn into 1, Then from 0 The place of dfs, But the time complexity is very high ！O(N * N * N * N)  Then trade space for time , Pass each block in advance dfs Well done , From 1 The place of dfs, Each location records the total number of connected blocks .  however , This will fail , because 0 The left and right connected blocks of may not be independent connected blocks , It may be the same connected block , It will lead to double calculation .  therefore , You need to number connected component blocks , Different connected component blocks can be added together . */
    public int largestIsland(int[][] grid) {
    
        int m = grid.length, n = grid[0].length;
        int max = 1 << 31;
        int[][][] f = new int[m][n][2];
        //  from 1 set out dfs
        int idx = 0;
        for (int i = 0; i < grid.length; i++) {
    
            for (int j = 0; j < grid[0].length; j++) {
    
                if (grid[i][j] == 1) {
    
                    int[] total = new int[]{
    0, idx};
                    dfs(grid, i, j, f, total);
                    max = Math.max(max, total[0]);
                    ++idx;
                }
            }
        }
        //  from 0 set out dfs.
        for (int i = 0; i < grid.length; i++) {
    
            for (int j = 0; j < grid[0].length; j++) {
    
                if (grid[i][j] == 0) {
    
                    int total = 1;
                    //  To duplicate the connected components 
                    Set<Integer> bool = new HashSet<>();
                    for (int[] gap : gaps) {
    
                        int ni = i + gap[0], nj = j + gap[1];
                        if (ni == -1 || -1 == nj || nj == grid[0].length || grid.length == ni || grid[ni][nj] == 0)
                            continue;
                        if (!bool.contains(f[i][j][1])) {
    
                            total += f[i][j][0];
                            bool.add(f[i][j][1]);
                        }
                    }
                    max = Math.max(max, total);
                }
            }
        }
        return max;
    }

    //  It is convenient to walk in four directions , Use matrix + The way of circulation .
    static final int[][] gaps = new int[][]{
    {
    1, 0}, {
    -1, 0}, {
    0, 1}, {
    0, -1}};

    //  How to make all nodes of a connected component be assigned to the total number of nodes .
    private void dfs(int[][] grid, int i, int j, int[][][] f, int[] total) {
    
        if (i == -1 || -1 == j || j == grid[0].length || grid.length == i || grid[i][j] <= 0) return;

        total[0]++;
        f[i][j] = total;

        grid[i][j] = -1;
        for (int[] gap : gaps) {
    
            int ni = i + gap[0], nj = j + gap[1];
            dfs(grid, ni, nj, f, total);
        }
    }
}

summary

1） The question is DFS+ Improved version of memory search , What you want to do is draw inferences from one instance , We must grasp the details firmly , For example, the visited needs are always marked , You can't leave it unmarked , You can't go back and remove the mark , This is not to find the maximum path value ; If the subscript is judged to be out of bounds , No i == 0 || i == n, yes i == -1 || i == n, This can be mistaken , I'm impressed .

2） Master these basic knowledge , According to the needs of the topic , To make corresponding use . For example, this topic can be a 0 become 1, Then it's better to start from 0 We're going to start traversing , Taking the maximum .

3） It's rather sad to do this today , Always feel that the idea is right （ But the idea is right , It's just that there's a hole that hasn't been found .）, It took a lot of time to find the key problem .（ The ability to find key problems is too weak , I think this is the core ability ！）. But don't be discouraged , Read the explanation of the question , Only to find that this is a hole deliberately given by the official , Need to break the comfort zone knowledge , Learn to draw inferences from one example , Grow step by step . So laugh if you want to lose , Read your thoughts out loud , If you can't figure it out, learn to solve the problem , This is a good time to break through yourself .

reference

[1] LeetCode The largest artificial island