You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.

Return the size of the largest island in grid after applying this operation.

An island is a 4-directionally connected group of 1s.

Example 1:

Input: grid = [[1,0],[0,1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2:

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

Example 3:

Input: grid = [[1,1],[1,1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.

Constraints:

• n == grid.length
• n == grid[i].length
• 1 <= n <= 500
• grid[i][j] is either 0 or 1.

最大人工岛。

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/making-a-large-island
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

既然是矩阵类型的题，那么思路还是偏 BFS/DFS 一类的。这道题我给出一个 DFS 的做法。题目问的是在 grid 中能否把其中某个 0 改成 1，使得某个岛屿的面积更大。这里有两个 corner case，一是如果整个 grid 都是岛，那么面积是不变的；另外一个 case 是如果整个 grid 都没有找到岛屿，那么最大面积只能是 1。

一般的情形是当我们找到了若干个岛屿（用不同的颜色标记）并知道了他们各自的面积之后，我们需要在每个岛屿边缘的外围上的每个点，看看这个点能否连到其他岛屿从而形成一个更大的岛屿。所以整体应该需要对 input 矩阵扫描两次，第一轮我们找到所有的岛屿，用不同颜色 color 标记，同时当我们找到岛屿边缘的时候，我们对岛屿的外圈上的点做个标记，我这里记为 -1。

第二轮再次扫描 input 矩阵的时候，我们只去找岛屿的外围上的点 -1。找到之后，我们看这个点的四个邻居能连到其他岛屿上从而形成一个更大的岛。

时间O(n^2)

空间O(n^2)

Java实现

 1 class Solution {
 2     public int largestIsland(int[][] grid) {
 3         HashMap<Integer, Integer> map = new HashMap<>();
 4         int color = 2; // 用不同的颜色标记找到的不同的岛
 5         int n = grid.length;
 6         for (int i = 0; i < n; i++) {
 7             for (int j = 0; j < n; j++) {
 8                 if (grid[i][j] == 1) {
 9                     int size = helper(grid, i, j, color);
10                     // corner case, if its all 1's
11                     if (size == n * n) {
12                         return size;
13                     }
14                     map.put(color, size);
15                     color++;
16                 }
17             }
18         }
19         // corner case
20         if (color == 2) {
21             return 1;
22         }
23 
24         int res = map.getOrDefault(2, 0);
25         for (int i = 0; i < n; i++) {
26             for (int j = 0; j < n; j++) {
27                 // 如果是岛的外围，则看看这个点能和多少已知的岛连起来组成更大的岛
28                 if (grid[i][j] == -1) {
29                     HashSet<Integer> set = new HashSet<>();
30                     set.add(i > 0 ? grid[i - 1][j] : 0);
31                     set.add(i < n - 1 ? grid[i + 1][j] : 0);
32                     set.add(j > 0 ? grid[i][j - 1] : 0);
33                     set.add(j < n - 1 ? grid[i][j + 1] : 0);
34 
35                     int newSize = 1;
36                     for (int c : set) {
37                         newSize += map.getOrDefault(c, 0);
38                     }
39                     res = Math.max(res, newSize);
40                 }
41             }
42         }
43         return res;
44     }
45 
46     private int helper(int[][] grid, int i, int j, int color) {
47         // 越界
48         if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) {
49             return 0;
50         }
51         if (grid[i][j] != 1) {
52             if (grid[i][j] == 0) {
53                 grid[i][j] = -1; // 标记成-1表示当前这个坐标是某个岛屿的外围
54             }
55             return 0;
56         }
57         grid[i][j] = color;
58         return 1 + helper(grid, i - 1, j, color) + helper(grid, i + 1, j, color) + helper(grid, i, j - 1, color)
59                 + helper(grid, i, j + 1, color);
60     }
61 }

 

flood fill题型总结

LeetCode 题目总结