827 最大人工岛

2024-01-07 10:28

文章标签 最大 827 人工岛

本文主要是介绍827 最大人工岛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

hard题目，十分困难哈，不是简单的岛屿套路，而是要经历过两次遍历，先一次遍历岛屿再一次遍历海洋

题目

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

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

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

示例 1:

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

代码与解析

class Solution {int n;Map<Integer, Integer> map = new HashMap<>();public int largestIsland(int[][] grid) {n = grid.length;int ans = 0;int index = 2;// 遍历整个 grid，标记陆地并计算各个岛屿的面积for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1) {int t = land(grid, i, j, index); // 标记岛屿并计算面积map.put(index, t); // 将岛屿编号和面积存入 mapindex++;ans = Math.max(ans, t); // 更新最大岛屿面积}}}// 处理全海洋情况if (ans == 0) return 1;// 遍历海洋区域，寻找合并后的最大岛屿面积for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 0) {HashSet<Integer> set = findNeighbor(grid, i, j); // 找到相邻岛屿if (set.size() < 1) continue; // 若无相邻岛屿，则跳过int t = 1;for (Integer m : set) t += map.get(m); // 计算合并后的岛屿面积ans = Math.max(ans, t); // 更新最大岛屿面积}}}return ans;}// 查找相邻的岛屿public HashSet<Integer> findNeighbor(int[][] grid, int x, int y) {HashSet<Integer> set = new HashSet<>();if (!notarea(x - 1, y) && grid[x - 1][y] != 0) set.add(grid[x - 1][y]);if (!notarea(x + 1, y) && grid[x + 1][y] != 0) set.add(grid[x + 1][y]);if (!notarea(x, y - 1) && grid[x][y - 1] != 0) set.add(grid[x][y - 1]);if (!notarea(x, y + 1) && grid[x][y + 1] != 0) set.add(grid[x][y + 1]);return set;}// 标记岛屿并计算面积public int land(int[][] grid, int x, int y, int index) {if (notarea(x, y) || grid[x][y] == 0) return 0;if (grid[x][y] != 1) return 0;grid[x][y] = index;int region = land(grid, x, y + 1, index) + land(grid, x, y - 1, index)+ land(grid, x + 1, y, index) + land(grid, x - 1, y, index);return region + 1;}// 判断是否超出边界public boolean notarea(int x, int y) {return x < 0 || y < 0 || x >= n || y >= n;}
}