LWC 53:695. Max Area of Island

LWC 53:695. Max Area of Island

传送门:695. Max Area of Island

Problem:

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water. Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:

[[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]] Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2:

[[0,0,0,0,0,0,0,0]] Given the above grid, return 0.

Note:

The length of each dimension in the given grid does not exceed 5

思路: DFS求出邻接的面积,更新每个区域的最大值即可。

代码如下:

    int[][] dir = {{1, 0},{-1, 0},{0, 1},{0, -1}};
    public int maxAreaOfIsland(int[][] grid) {
        int n = grid.length;
        if (n == 0) return 0;
        int m = grid[0].length;
        if (m == 0) return 0;

        int max = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 1) {
                    max = Math.max(max, dfs(grid, i, j, n, m, new boolean[n][m]));
                }
            }
        }

        return max;
    }

    public int dfs(int[][] grid, int i, int j, int n, int m, boolean[][] vis) {
        int res = 1;
        vis[i][j] = true;
        for (int[] d : dir) {
            int nx = i + d[0];
            int ny = j + d[1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && grid[nx][ny] == 1) {
                res += dfs(grid, nx, ny, n, m, vis);
            }
        }
        return res;
    }    

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏云瓣

JS 装饰器解析

随着 ES6 和 TypeScript 中类的引入,在某些场景需要在不改变原有类和类属性的基础上扩展些功能,这也是装饰器出现的原因。 装饰器简介 作为一种可以动...

3125
来自专栏noteless

[二十三]JavaIO之PushbackReader

PushBackReader 与 PushBackInputStream实现的原理是一样的

952
来自专栏Android开发指南

用最简单的例子说明设计模式(一)之单例模式、工厂模式、装饰模式、外观模式

4155
来自专栏算法修养

PAT 1004 Counting Leaves

1004. Counting Leaves (30) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B ...

3778
来自专栏草根专栏

.NET Core装饰模式和.NET Core的Stream

Beverage是所有咖啡饮料的抽象类, 里面的cost方法是抽象的. description变量在每个子类里面都需要设置(表示对咖啡的描述).

41713
来自专栏计算机视觉与深度学习基础

Leetcode 210 Course Schedule II 拓扑排序

There are a total of n courses you have to take, labeled from 0 to n - 1. Som...

2145
来自专栏chenssy

【死磕 Spring】----- IOC 之解析自定义标签

在博客 【死磕Spring】----- IOC 之 注册 BeanDefinition 中提到:获取 Document 对象后,会根据该对象和 Resource...

1143
来自专栏算法修养

pta 习题集5-19 列车厢调度

1 ====== <--移动方向 / 3 ===== \ 2 ====== ...

2966
来自专栏技术点滴

装饰者模式(Decorator)

装饰者模式(Decorator) 装饰者模式(Decorator)[Wrapper] 意图:动态的给一个对象添加一些额外的职责,就增加功能来说,比生成子类更为灵...

2017
来自专栏草根专栏

用.NET Core实现装饰模式和.NET Core的Stream简介

该文章综合了几本书的内容. 某咖啡店项目的解决方案 ? 某咖啡店供应咖啡, 客户买咖啡的时候可以添加若干调味料, 最后要求算出总价钱. Beverage是所有咖...

5595

扫码关注云+社区