1. 827. Maximum artificial island (depth first)

On a two-dimensional map, 0 represents the ocean and 1 represents the land. We can only change a grid of 0 oceans into a land at most.

What is the area of the largest island on the map after reclamation? (1 islands connected in the upper, lower, left and right directions)

Example 1:

Input: [[1, 0], [0, 1]]
Output: 3
Interpretation: Turn a grid 0 into a grid 1, and eventually connect the two islands to an island of 3.

Example 2:

Input: [[1, 1], [1, 0]]
Output: 4
Explanation: Change the grid 0 to 1 and expand the island area to 4.

Example 3:

Input: [[1, 1], [1, 1]]
Output: 4
Explanation: No 0 can make us 1, and the area is still 4.

Explain:

1 <= grid.length = grid[0].length <= 50
0 <= grid[i][j] <= 1

public int largestIsland(int[][] grid) {
        if (grid == null || grid.length == 0)
            return 0;

        int max = 0;
        int row = grid.length;
        int col = grid[0].length;
        //There must be this, in order to solve this situation {{1}}
        boolean hasZero = false;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 0) {
                    hasZero = true;
                    grid[i][j] = 1;
                    int cur = dfs(grid, i, j, row, col, new boolean[row][col]);
                    if (cur == row * col)
                        return cur;

                    if (cur > max) {
                        max = cur;
                    }
                    grid[i][j] = 0;
                }
            }
        }
        return hasZero ? max : row * col;
    }

    private int dfs(int[][] grid, int i, int j, int row, int col, boolean[][] booleans) {
        //In this case, return 0
        if (i < 0 || j < 0 || i >= row || j >= col || grid[i][j] == 0 || booleans[i][j])
            return 0;

        booleans[i][j] = true;
        return 1 + dfs(grid, i + 1, j, row, col, booleans) + dfs(grid, i - 1, j, row, col, booleans) + dfs(grid, i, j + 1, row, col, booleans) + dfs(grid, i, j - 1, row, col, booleans);
    }

2. Beijing East 2019 Spring Call Written Examination (Fire, Depth First)

Train of thought:
Find the left and right subtrees of the root node, and the number of nodes is the most.

//Depth first
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String nStr = sc.nextLine();
            int n = Integer.parseInt(nStr);
            int[][] edges = new int[n][2];
            for (int i = 0; i < n - 1; i++) {
                String str = sc.nextLine();
                String[] strings = str.split(" ");
                edges[i][0] = Integer.parseInt(strings[0]);
                edges[i][1] = Integer.parseInt(strings[1]);
            }

            HashMap<Integer, ArrayList<Integer>> hashMap = new HashMap<>();
            for (int i = 0; i < n; i++) {
                if (hashMap.containsKey(edges[i][1])) {
                    hashMap.get(edges[i][1]).add(edges[i][0]);
                } else {
                    ArrayList<Integer> arrayList = new ArrayList<>();
                    arrayList.add(edges[i][0]);
                    hashMap.put(edges[i][1], arrayList);
                }
            }
            ArrayList<Integer> arrayList = hashMap.get(1);
            int res = 0;
            for (int i : arrayList) {
                int temp = dfs(hashMap, i);
                if (temp > res) {
                    res = temp;
                }
            }
            System.out.println(res);
        }
    }

    private static int dfs(HashMap<Integer, ArrayList<Integer>> hashMap, int num) {
        int count = 1;
        if (hashMap.get(num) == null)
            return count;
        for (int i : hashMap.get(num)) {
            count += dfs(hashMap, i);
        }
        return count;
    }

3,

Given a non-spatial two-dimensional array grid containing some zeros and ones, an island is a combination of four directions (horizontal or vertical) of one (representing land). You can assume that the four edges of a two-dimensional matrix are surrounded by water.

Find the largest island area in a given two-dimensional array. (If there are no islands, the return area is 0. )

Example 1:

For the given matrix above, return 6. Note that the answer should not be 11, because the islands can only contain `1'in four horizontal or vertical directions.

Example 2:

[[0,0,0,0,0,0,0,0]]

For the given matrix above, return 0.

Note: The length and width of a given matrix grid are not more than 50.

Code:

Note: After traversing grid[i][j]=1, make grid[i][j]=-1

public int maxAreaOfIsland(int[][] grid) {
        int row=grid.length;
        int col=grid[0].length;

        int max=0;

        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]==1){
                    int cur=dfs(grid,i,j,row,col);
                    if(cur==row*col){
                        return cur;
                    }
                    if(cur>max){
                        max=cur;
                    }
                }
            }
        }
        return max;
    }

    private int dfs(int[][] grid, int i, int j, int row, int col) {
        if(i<0||j<0||i>=row||j>=col||grid[i][j]==0||grid[i][j]==-1)
            return 0;

        grid[i][j]=-1;
        return 1+dfs(grid,i+1,j,row,col)+dfs(grid,i-1,j,row,col)+dfs(grid,i,j+1,row,col)+dfs(grid,i,j-1,row,col);
    }