Java实现 LeetCode 827 最大人工岛（DFS+暴力模拟）

雨点打透心脏的1/2处 2023-03-13 03:46 49阅读 0赞

## 827. 最大人工岛 ##

在二维地图上， 0代表海洋， 1代表陆地，我们最多只能将一格 0 海洋变成 1变成陆地。

进行填海之后，地图上最大的岛屿面积是多少？（上、下、左、右四个方向相连的 1 可形成岛屿）

示例 1:

输入: \[\[1, 0\], \[0, 1\]\]  
输出: 3  
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。  
示例 2:

输入: \[\[1, 1\], \[1, 0\]\]  
输出: 4  
解释: 将一格0变成1，岛屿的面积扩大为 4。  
示例 3:

输入: \[\[1, 1\], \[1, 1\]\]  
输出: 4  
解释: 没有0可以让我们变成1，面积依然为 4。  
说明:

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

PS：  
DFS把岛屿拿出来，每个岛屿放上不同的标记  
然后，把每个岛屿的面积放进数组存上，  
然后再找每一个海洋，看看要是能把当前海洋变成陆地，组成的最大的面积是多少记录一下

class Solution { 
         public int largestIsland(int[][] grid) { 
            int[] map = new int[grid.length*grid[0].length/2+3];
            int index = 2;
            for (int i = 0; i < grid.length; i++) { 
                for (int j = 0; j < grid[0].length; j++) { 
                    if (grid[i][j] == 1) { 
                        fullIsland(grid, i, j, index++);
                    }
                }
            }
            for (int i = 0; i < grid.length; i++) { 
                for (int j = 0; j < grid[0].length; j++) { 
                    if (grid[i][j] > 0) { 
                        map[grid[i][j]]++;
                    }
                }
            }
            int max = 0;
            for (int i = 0; i < grid.length; i++) { 
                for (int j = 0; j < grid[0].length; j++) { 
                    if (grid[i][j] == 0) { 
                        int t = 1,t1=0,t2=0,t3=0,t4=0;
                        if (i > 0 && (t1 = grid[i - 1][j]) > 1) { 
                            t += map[t1];
                        }
                        if (i < grid.length - 1 && (t2 = grid[i + 1][j]) > 1 && t2 !=t1) { 
                            t += map[t2];
                        }
                        if (j > 0 && (t3 = grid[i][j - 1]) > 1 && t2 !=t3 && t1 !=t3) { 
                            t += map[t3];
                        }
                        if (j < grid[0].length - 1 && (t4 = grid[i][j + 1]) > 1 && t4 != t3 && t2 != t4 && t1 != t4) { 
                            t += map[t4];
                        }
                        max = Math.max(max, t);
                    }
                }
            }
            if (max == 0) { 
                if (grid[0][0] == 0) { 
                    return 1;
                } else { 
                    return grid.length*grid[0].length;
                }
            }
            return max;
        }
    
        public void fullIsland(int[][] grid, int i, int j, int index) { 
            grid[i][j] = index;
            if (i > 0 && grid[i - 1][j] == 1) { 
                fullIsland(grid, i - 1, j, index);
            }
            if (i < grid.length - 1 && grid[i + 1][j] == 1) { 
                fullIsland(grid, i + 1, j, index);
            }
            if (j > 0 && grid[i][j - 1] == 1) { 
                fullIsland(grid, i, j - 1, index);
            }
            if (j < grid[0].length - 1 && grid[i][j + 1] == 1) { 
                fullIsland(grid, i, j + 1, index);
            }
        }
    }