Making A Large Island

题目
In a 2D grid of 0s and 1s, we change at most one 0 to a 1.

After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).

答案
如果你想到的思路是
把某点设成1，然后取整个grid最大island的大小，那么时间复杂度是O(n^3)，估计是会TLE的

更高效的方法是，用一遍dfs把每个island的大小算出来，然后用map记录每个cell对应的岛屿大小是多少。
然后，对于每个value为0的cell，试图把它周围的岛屿连起来有多大，返回最大者

class Solution {
    int island = 2;
    int max_island_size = 0;
    int[][] delta = new int[][]{{0, 1},{0 , -1},{1, 0},{-1, 0}};
    Map<Integer, Integer> map = new HashMap<>();

    public int largestIsland(int[][] grid) {
        int island_sum_max = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == 1) {
                    map.put(island, 0);
                    dfs_island_size(grid, i, j);
                    island++;
                }
            }
        }

        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                Set<Integer> set = new HashSet<>();
                if(grid[i][j] == 0) {
                    // Look at 4 directions
                    int island_sum = 0;
                    for(int k = 0; k < 4; k++) {
                        int ni = i + delta[k][0];
                        int nj = j + delta[k][1];
                        if(ni < 0 || ni >= grid.length || nj < 0 || nj >= grid[0].length || grid[ni][nj] == 0)
                            continue;
                        if(!set.contains(grid[ni][nj])) {
                            set.add(grid[ni][nj]);
                            island_sum += map.get(grid[ni][nj]);
                        }
                    }
                    island_sum_max = Math.max(island_sum_max, island_sum);
                }
            }
        }
        return Math.max(island_sum_max + 1, max_island_size);
    }

    public void dfs_island_size(int[][] grid, int i, int j) {
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1)
            return;
        // Mark as visited
        grid[i][j] = island;
        // Set size
        int island_size = map.get(island) + 1;
        max_island_size = Math.max(max_island_size, island_size);
        map.put(island, island_size);

        for(int k = 0; k < 4; k++) {
            int ni = i + delta[k][0];
            int nj = j + delta[k][1];
            dfs_island_size(grid, ni, nj);
        }
    }
}