827. 最大人工岛

深度优先搜索

import java.util.ArrayList;
import java.util.HashMap;

class Solution {

    int m;
    int n;
    boolean[][] used;
    int[][] move = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int largestIsland(int[][] grid) {

        m = grid.length;
        n = grid[0].length;
        int num = 2;
        int max = 0;
        used = new boolean[m][n];
        HashMap map = new HashMap<>();

        /**
         * 先按照《695. 岛屿的最大面积》求出所有可能的面积，用HashMap记录
         * 为了区别不同的岛屿，将每个岛的值更改为从2开始的序列
         * 同时还要记录下最大的岛屿面积，因为有可能不存在0，这样结果就是这个最大值
         */
        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                if (grid[i][j] == 1 && !used[i][j]) {

                    int result = dfs(grid, i, j, num);
                    max = Math.max(max, result);
                    map.put(num, result);
                    num++;
                }
            }
        }

        /**
         * 在求出所有的岛屿面积以后，从头开始寻找0
         * 每找到一个0就遍历它的四周，统计四周岛屿的总面积，注意res还要包括这个0的位置
         * 注意，有可能四周的岛屿是同一个岛屿，为了避免重复统计，用列表记录下统计过的岛屿
         */
        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                if (grid[i][j] == 0) {

                    /**
                     * 起始大小包括这个0位本身
                     */
                    int res = 1;
                    ArrayList list = new ArrayList<>();

                    for (int k = 0; k < 4; k++) {

                        int newRow = i + move[k][0];
                        int newCol = j + move[k][1];

                        if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] != 0 && !list.contains(grid[newRow][newCol])) {

                            res += map.get(grid[newRow][newCol]);
                            list.add(grid[newRow][newCol]);
                        }
                    }

                    max = Math.max(max, res);
                }
            }
        }

        return max;

    }

    public int dfs(int[][] grid, int row, int col, int num) {

        /**
         * 将每个岛屿的值更改为从2开始的序列
         */
        used[row][col] = true;
        grid[row][col] = num;
        int sum = 1;

        for (int i = 0; i < 4; i++) {

            int newRow = row + move[i][0];
            int newCol = col + move[i][1];

            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !used[newRow][newCol] && grid[newRow][newCol] == 1) {
                sum += dfs(grid, newRow, newCol, num);
            }
        }

        return sum;
    }
}

/**
 * 时间复杂度 O(m×n)
 * 空间复杂度 O(m×n)
 */

https://leetcode-cn.com/problems/making-a-large-island/