Daily LeetCode – day0051 0827. Making A Large Island

import java.util.HashSet;

// 0827. Making A Large Island
class Solution {
    public int largestIsland(int[][] grid) {
        int n = grid.length;
        int fillNumber = 2;
        int[][] dxdy = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    dfs(i, j, fillNumber, grid, dxdy, n);
                    ++fillNumber;
                }
            }
        }
        int[] areas = new int[fillNumber + 1];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                ++areas[grid[i][j]];
            }
        }
        if (areas[2] == 0) return 1;
        if (areas[0] == 0) return n * n;
        int ans = 0;
        HashSet<Integer> around = new HashSet<>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    int total = 1;
                    around.clear();
                    if (i - 1 >= 0 && grid[i - 1][j] != 0) around.add(grid[i - 1][j]);
                    if (j + 1 < n && grid[i][j + 1] != 0) around.add(grid[i][j + 1]);
                    if (i + 1 < n && grid[i + 1][j] != 0) around.add(grid[i + 1][j]);
                    if (j - 1 >= 0 && grid[i][j - 1] != 0) around.add(grid[i][j - 1]);
                    for (Integer a : around) {
                        total += areas[a];
                    }
                    if (total > ans) ans = total;
                }
            }
        }
        return ans;
    }

    void dfs(int x, int y, int fillNumber, int[][] grid, int[][] dxdy, int n) {
        grid[x][y] = fillNumber;
        for (int[] d : dxdy) {
            int nx = x + d[0];
            int ny = y + d[1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                dfs(nx, ny, fillNumber, grid, dxdy, n);
            }
        }
    }
}

学习笔记：
这是一道深度优先搜索的题目，说是困难题，但可能我深搜掌握的还可以。还用到了集合去重。
首先把每个1都多源深搜，标注成不同数字从2开始的岛屿。
然后从每个0开始尝试，0可以联通上下左右的岛屿，但是如果0的上下左右的岛屿有编号相同那就只能加一遍，所以用到了集合去重，0变成陆地后还需要额外加一。