leetcode 695. Max Area of Island 岛屿的最大面积 (中等)

作者：okokabcd

2022 年 5 月 31 日
本文字数：1020 字
阅读完需：约 3 分钟

leetcode 695. Max Area of Island 岛屿的最大面积(中等)

一、题目大意

标签: 搜索

https://leetcode.cn/problems/max-area-of-island

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直的四个方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]输出：6 解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

示例 2：

输入：grid = [[0,0,0,0,0,0,0,0]]输出：0

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] 为 0 或 1

二、解题思路

搜索类的题，这题可以用深度优先搜索，定义一个主函数和一个辅函数，主函数用于遍历所有的搜索位置，判断是否可以开始搜索，辅函数则负责深度优先搜索的递归调用。

三、解题方法

3.1 Java 实现

public class Solution {    public int maxAreaOfIsland(int[][] grid) {        this.GRID = grid;        this.M = grid.length;        this.N = grid[0].length;        for (int i = 0; i < M; i++) {            for (int j = 0; j < N; j++) {                if (GRID[i][j] == 1) {                    dfs(i, j);                    max = Math.max(max, island);                    island = 0;                }            }        }        return max;    }
    private int[][] GRID;    private int M;    private int N;    private int[][] dirs = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};    private int island = 0;    private int max = 0;
    private void dfs(int i, int j) {        // 此处保证GRID[i][j] == 1        GRID[i][j] = 0;        island++;        for (int[] dir : dirs) {            int x = i + dir[0];            int y = j + dir[1];            if (x >= 0 && x < M && y >= 0 && y < N && GRID[x][y] == 1) {                dfs(x, y);            }        }    }}

复制代码

四、总结小记

2022/5/31 5 月最后一天啦

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/9308011fc389566f946a39f86】。文章转载请联系作者。

okokabcd

关注

还未添加个人签名 2019.11.15 加入

还未添加个人简介

发布

暂无评论

创作场景