827. 最大人工岛

题目链接

827. 最大人工岛

思路

这道题目可以使用深度优先搜索（DFS）来解决。首先，我们需要遍历整个地图，找到每个人工岛，并给它们标记一个唯一的编号。然后，我们再次遍历整个地图，对于每个海洋格子，我们可以通过查看它上下左右四个方向的格子来判断是否可以与其相连。如果可以相连，我们就将相连的人工岛的面积相加，并更新最大的人工岛面积。

解题方法

1. 首先，我们需要遍历整个地图，找到每个人工岛，并给它们标记一个唯一的编号。我们可以使用DFS来实现这一步骤。对于每个为1的格子，我们将其标记为当前的编号，并递归地将与其相连的格子也标记为当前的编号。2. 然后，我们再次遍历整个地图，对于每个海洋格子，我们可以通过查看它上下左右四个方向的格子来判断是否可以与其相连。如果可以相连，我们就将相连的人工岛的面积相加，并更新最大的人工岛面积。

复杂度

时间复杂度: O(nm)，其中n和m分别为地图的行数和列数。空间复杂度: O(nm)，需要使用一个大小为n*m的visited数组来记录每个格子是否被访问过。

代码

class Solution {
    public int largestIsland(int[][] grid) {
        // 首先感染每一个人工岛 并且用id标记编号
        int n = grid.length;
        int m = grid[0].length;
        int id = 2;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    dfs(grid, n, m, i, j, id++);
                }
            }
        }
        int ans = 0;
        int[] sizes = new int[id];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] > 1) {
                    ans = Math.max(ans, ++sizes[grid[i][j]]);
                }
            }
        }

        boolean[] visited = new boolean[id];
        int up, left, down, right, merge;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) {
                    up = i > 0 ? grid[i - 1][j] : 0;
                    down = i < n - 1 ? grid[i + 1][j] : 0;
                    left = j > 0 ? grid[i][j - 1] : 0;
                    right = j < m - 1 ? grid[i][j + 1] : 0;
                    visited[up] = true;
                    merge = 1 + sizes[up];
                    if (!visited[down]) {
                        visited[down] = true;
                        merge += sizes[down];
                    }
                    if (!visited[left]) {
                        visited[left] = true;
                        merge += sizes[left];
                    }
                    if (!visited[right]) {
                        visited[right] = true;
                        merge += sizes[right];
                    }
                    ans = Math.max(ans, merge);
                    visited[up] = false;
                    visited[down] = false;
                    visited[left] = false;
                    visited[right] = false;
                }
            }
        }
        return ans;

    }

    public void dfs(int[][] grid, int n, int m, int i, int j, int id) {
        if (i < 0 || i == n || j < 0 || j == m || grid[i][j] != 1) {
            return;
        }
        grid[i][j] = id;
        dfs(grid, n, m, i + 1, j, id);
        dfs(grid, n, m, i - 1, j, id);
        dfs(grid, n, m, i, j + 1, id);
        dfs(grid, n, m, i, j - 1, id);
    }
}

以上是对题目827. 最大人工岛的解题思路和代码的介绍。

原文地址：https://blog.csdn.net/m0_73939789/article/details/135860795

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！