岛屿的最大面积

[编程题]岛屿的最大面积

热度指数：3024 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个用 n*m 矩阵表示的群岛的地图，其中 1 表示岛屿， 0 表示海洋，每个岛屿的水平或竖直方向相邻的岛屿可以视为连在一起的岛屿，每一块岛屿视为面积为 1 ，请问面积最大的岛屿是多少。

例如：

当输入[[1,0],[0,1]]时，对应的地图为：

只有在水平或竖直方向相邻的岛屿可以连在一起，所以每个岛屿互相独立。最大面积是1

当输入[[1,1],[1,0]]时，对应的地图为：

三块岛屿可以连在一起，最大面积是3

数据范围： $1 \le n,m \le 50$

示例1

输入

[[1,0],[0,1]]

输出

说明

如题面解释

示例2

输入

[[1,1],[1,0]]

输出

说明

如题面解释

示例3

输入

[[0]]

输出

算法知识视频讲解

小谷围做题家

package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param grid int整型二维数组 
 * @return int整型
*/
func maxAreaIsland( grid [][]int ) int {
    n,m:=len(grid),len(grid[0])
    cnt:=0
    var dfs func(int,int)
    dfs=func(i,j int){
        if i<0||i>=n||j<0||j>=m||grid[i][j]==0{
            return
        }
        grid[i][j]=0
        cnt++
        dfs(i+1,j)
        dfs(i,j+1)
        dfs(i-1,j)
        dfs(i,j-1)
    }
    ans:=0
    for i:=0;i<n;i++{
        for j:=0;j<m;j++{
            if grid[i][j]==1{
                cnt=0
                dfs(i,j)
                if cnt>ans{
                    ans=cnt
                }
            }
        }
    }
    return ans
}

发表于 2023-03-08 00:00:22 回复(0)

王飞-6

dfs即可

func maxAreaIsland( grid [][]int ) (max int) {
    row, col := len(grid), len(grid[0])
    var dfs func(int, int) int
    dfs = func(x, y int) int {
        if x < 0 || x >= row || y < 0 || y >= col || grid[x][y] == 0 {
            return 0
        }
        grid[x][y]=0
        return dfs(x+1, y) + dfs(x, y+1) + dfs(x-1, y) + dfs(x, y-1) + 1
    }
    for x:=0; x < row; x++ {
        for y:=0; y < col; y++ {
            if grid[x][y] == 1 {
                tmp := dfs(x, y)
                if tmp > max {
                    max = tmp
                }
            }
        }
    }
    return
}

发表于 2021-11-23 16:37:43 回复(0)