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

相关文章

来自专栏HansBug's Lab

1441: Min

1441: Min Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 320  Solved: 213 [Submi...

1824
来自专栏小樱的经验随笔

Codeforces 839B Game of the Rows【贪心】

B. Game of the Rows time limit per test:1 second memory limit per test:256 megab...

3166
来自专栏HansBug's Lab

3381: [Usaco2004 Open]Cave Cows 2 洞穴里的牛之二

3381: [Usaco2004 Open]Cave Cows 2 洞穴里的牛之二 Time Limit: 10 Sec  Memory Limit: 128 ...

2727
来自专栏算法修养

HDU 4059 The Boss on Mars(容斥原理)

The Boss on Mars Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/...

3285
来自专栏算法修养

Code Forces 149DColoring Brackets(区间DP)

 Coloring Brackets time limit per test 2 seconds memory limit per test 256...

2816
来自专栏专知

【Leetcode 70】关关的刷题日记68 – Leetcode 70 Climbing Stairs

关关的刷题日记68 – Leetcode 70 Climbing Stairs 题目 You are climbing a stair case. It tak...

2707
来自专栏ml

hdu 4034 Graph (floyd的深入理解)

Graph Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65768/65768 K (Jav...

33711
来自专栏HansBug's Lab

3360: [Usaco2004 Jan]算二十四

3360: [Usaco2004 Jan]算二十四 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 6  So...

3144
来自专栏小樱的经验随笔

Codeforces Round #411 (Div. 2)(A,B,C,D 四水题)

A. Fake NP time limit per test:1 second memory limit per test:256 megabytes inpu...

2726
来自专栏ml

hdu---(Tell me the area)(几何/三角形面积以及圆面积的一些知识)

Tell me the area Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65536/3...

3487

扫码关注云+社区