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 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

Go语言轻量级线程Goroutine用法实例

本文实例讲述了Go语言轻量级线程Goroutine用法。分享给大家供大家参考。具体如下: goroutine 是由 Go 运行时环境管理的轻量级线程。 go f...

4039
来自专栏Golang语言社区

Go语言轻量级线程Goroutine用法实例

本文实例讲述了Go语言轻量级线程Goroutine用法。分享给大家供大家参考。具体如下: goroutine 是由 Go 运行时环境管理的轻量级线程。 go f...

33711
来自专栏和蔼的张星的图像处理专栏

365. 二进制中有多少个1

思路一:遍历每一位,如果是1,计数器加1即可,也是最容易想到的,需要遍历一次,可以用不断除2来做,也可以用位操作,后者更简单些:

752
来自专栏LinXunFeng的专栏

iOS - Swift 创建代理协议的多种方式

1413
来自专栏java初学

final和static关键字

33911
来自专栏后端技术探索

PHP主动断开与浏览器的连接

曾经整理过一篇《关于PHP连接处理中set_time_limit()、connection_status()和ignore_user_abort()深入解析》

592
来自专栏Java Edge

注解机制及其原理什么是注解注解的使用注解的原理

31914
来自专栏技术博文

php 中file_get_contents超时问题的解决方法

最近开发遇到一个file_get_contents超时的问题,主要是因为访问腾讯服务器导致php脚本超时,下面我来总结file_get_contents超时问题...

2967
来自专栏软件开发 -- 分享 互助 成长

文件重定向函数freopen

头文件:stdio.h FILE *freopen( const char *filename, const char *mode, FILE *stream ...

1747
来自专栏软件开发 -- 分享 互助 成长

C++初始化列表

一、什么是初始化列表 与其他函数不同,构造函数除了有名字,参数列表和函数体之外,还可以有初始化列表,初始化列表以冒号开头,后跟一系列以逗号分隔的初始化字段 二、...

1799

扫码关注云+社区