[LeetCode]827.MakingALargeIsland

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 map = new HashMap<>();
4 int color = 2; // 用不同的颜色标记找到的不同的岛
5 int n = grid.length;
6 for (int i = 0; i 7 for (int j = 0; 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 26 for (int j = 0; j 27 // 如果是岛的外围，则看看这个点能和多少已知的岛连起来组成更大的岛
28 if (grid[i][j] == -1) {
29 HashSet set = new HashSet<>();
30 set.add(i > 0 ? grid[i - 1][j] : 0);
31 set.add(i 32 set.add(j > 0 ? grid[i][j - 1] : 0);
33 set.add(j 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 题目总结