首页 > 试题广场 >

岛屿的最大面积

[编程题]岛屿的最大面积
  • 热度指数：2964 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个用 n*m 矩阵表示的群岛的地图，其中 1 表示岛屿， 0 表示海洋，每个岛屿的水平或竖直方向相邻的岛屿可以视为连在一起的岛屿，每一块岛屿视为面积为 1 ，请问面积最大的岛屿是多少。

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

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

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

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

数据范围：
示例1

输入

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

输出

1

说明

如题面解释
示例2

输入

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

输出

3

说明

如题面解释
示例3

输入

[[0]]

输出

0
算法知识视频讲解
添加回答
Leeston520头像 Leeston520
这道题使用记忆化搜索优化dfs过程，思路较简单，很容易想到解法： 

static int res = 0;

    public static int maxAreaIsland(int[][] grid) {
        // write code here
        if (grid == null)
            return 0;

        int xLen = grid.length;
        int yLen = grid[0].length;

        boolean[][] hasDone = new boolean[xLen][yLen];
        int maxAria = 0;
        for (int i = 0; i < xLen; i++) {
            for (int j = 0; j < yLen; j++) {
                if (!hasDone[i][j] && grid[i][j] == 1) {
                    recursiveHelper(i, j, grid, hasDone, maxAria);
                }
            }
        }

        return res;
    }

    public static int recursiveHelper(int x, int y, int[][] grid, boolean[][] hasDone, int maxAria) {
        // 开始递归
        if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && !hasDone[x][y] && grid[x][y] == 1) {
            maxAria++;
            res = Math.max(maxAria, res);

            hasDone[x][y] = true;
            // 右边
            maxAria = recursiveHelper(x + 1, y, grid, hasDone, maxAria);
            // 左边
            maxAria = recursiveHelper(x - 1, y, grid, hasDone, maxAria);
            // 上边
            maxAria = recursiveHelper(x, y + 1, grid, hasDone, maxAria);
            // 下边
            maxAria = recursiveHelper(x, y - 1, grid, hasDone, maxAria);

        }
        return maxAria;
    }


发表于 2024-05-02 18:10:55 回复(0)
Python3
liangzhengjie头像 liangzhengjie 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param grid int整型二维数组 
# @return int整型
#
class Solution:
    def maxAreaIsland(self , grid: List[List[int]]) -> int:
        # write code here
        visited = [[False for j in range(len(grid[0]))] for i in range(len(grid))]

        max_n = 0

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if not visited[i][j] and grid[i][j] == 1:
                    tmp = self.traverse(grid, visited, i,j)
                    max_n = max(max_n, tmp)
        return max_n

    def traverse(self, grid, visited, x, y):
        if grid[x][y] == 0&nbs***bsp;visited[x][y] == True:
            return 0

        tmp = 1
        visited[x][y] = True
        if x - 1 > 0:
            tmp += self.traverse(grid, visited, x-1, y)

        if x + 1 < len(grid):
            tmp += self.traverse(grid, visited, x+1, y)

        if y-1 > 0:
            tmp += self.traverse(grid, visited, x, y-1)

        if y + 1<len(grid[0]):
            tmp += self.traverse(grid, visited, x, y+1)


        return tmp

发表于 2024-04-14 00:32:40 回复(0)
Java
梁山教父头像 梁山教父 
import java.util.*;


public class Solution {
    int now=0;
    int max=0;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型二维数组 
     * @return int整型
     */
    public int maxAreaIsland (int[][] grid) {
        // write code here
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[i].length;j++){
                if(grid[i][j]==1){
                    dfs(grid,i,j);
                }
                now=0;
            }
        }
        return max;
    }
    public void dfs(int[][] grid,int x,int y){
        if(now>max){
            max=now;
        }
        if(x>=0&&x<grid.length&&y>=0&&y<grid[0].length&&grid[x][y]==1){
            now++;
            grid[x][y]=0;
            dfs(grid,x+1,y);
            dfs(grid,x-1,y);
            dfs(grid,x,y+1);
            dfs(grid,x,y-1);
        }
    }
}

发表于 2023-05-18 17:03:16 回复(0)
Go
小谷围做题家头像 小谷围做题家 
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)
C
企鹅暴打皮卡丘头像 企鹅暴打皮卡丘
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param grid int整型二维数组 
 * @param gridRowLen int grid数组行数
 * @param gridColLen int* grid数组列数
 * @return int整型
 */
 int max(int a,int b)
 {
     if(a>b)
     return a;
     return b;
 }
 int dfs(int **grid,int **visit,int i,int j,int n,int m)
 {
    visit[i][j]=1;
    int square=1;
    if(i-1>0 && visit[i-1][j]==0 &&grid[i-1][j]==1)
        square=square+dfs(grid,visit,i-1,j,n,m);
    if(i+1<n && visit[i+1][j]==0 &&grid[i+1][j]==1)
        square=square+dfs(grid,visit,i+1,j,n,m);
    if(j+1<m && visit[i][j+1]==0 &&grid[i][j+1]==1)
        square=square+dfs(grid,visit,i,j+1,n,m);
    if(j-1>0 && visit[i][j-1]==0 &&grid[i][j-1]==1)
        square=square+dfs(grid,visit,i,j-1,n,m);
     return square;
 }
int maxAreaIsland(int** grid, int gridRowLen, int* gridColLen ) {
    int n=*gridColLen;
    int m=gridRowLen;
    int maxsquare=0;
    int **visit;
    visit=(int**)malloc(sizeof(int*)*m);
    for(int i=0;i<m;i++)
        visit[i]=(int*)malloc(sizeof(int)*n);
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
            visit[i][j]=0;
    }
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(grid[i][j]==1 && visit[i][j]==0)
            {
                maxsquare=max(dfs(grid,visit,i,j,m,n),maxsquare);
            }
        }
    }
    return maxsquare;
}
发表于 2022-09-30 11:01:31 回复(0)
C++
zhengluoqi头像 zhengluoqi 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int m,n,t;
    void dfs(vector<vector<int> >& grid,int i,int j){
        grid[i][j]=0;
        if(i>0&&grid[i-1][j]==1){
            t++;
            dfs(grid,i-1,j);
        }
        if(i<grid.size()-1&&grid[i+1][j]){
            t++;
            dfs(grid,i+1,j);
        }
        if(j>0&&grid[i][j-1]){
            t++;
            dfs(grid,i,j-1);
        }
        if(j<grid.size()-1&&grid[i][j+1]){
            t++;
            dfs(grid,i,j+1);
        }
        return;
    }
    int maxAreaIsland(vector<vector<int> >& grid) {
        // write code here
        n=grid.size();
        if(n==0)return 0;
        int ans=0;
        m=grid[0].size();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]==1){
                    t=1;
                    dfs(grid,i,j);
                    ans=max(ans,t);
                }
            }
        }
        return ans;
    }
};

发表于 2022-08-04 17:02:51 回复(0)
Java
pickpig头像 pickpig 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型二维数组 
     * @return int整型
     */
    int [][] visited;
    int [][] disrs = new int[][] {{0,1},{0,-1},{1,0},{-1,0}};
    public int maxAreaIsland (int[][] grid) {
        // write code here
        //深度优先遍历
        int n = grid.length;   //行
        int m = grid[0].length;  //列
        visited = new int[n][m];
        int maxSquare = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] != '0' && visited[i][j] != 1) {
                    maxSquare = Math.max(dfs(grid,i,j,n,m),maxSquare);
                }
            }
        }
        return maxSquare;
    }
    public int dfs(int[][] grid,int x, int y,int n,int m) {
        int square = 0;
        if(x < 0 || y < 0 || x >= n || y >= m) {
            return 0;
        }
        if(grid[x][y] == 0) {
            return 0;
        }
        if(visited[x][y] == 1) {   //表示已经1遍历过，就不再计算。
            return 0;
        }
        visited[x][y] = 1;
        square++;
        for(int i = 0; i < 4; i++) {
            int nextX = x + disrs[i][0];
            int nextY = y + disrs[i][1];
            square += dfs(grid,nextX,nextY,n,m);
        }
        return square;
    }
}

发表于 2022-06-28 13:33:38 回复(0)
C++
牛客487629784号头像 牛客487629784号 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int maxAreaIsland(vector<vector<int> >& grid) {
        // write code here
        int maxx=0;
        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[0].size();j++)
            {
                int tmp=help(grid,i,j,0);
                maxx=max(maxx,tmp);
            }
        }
        return maxx;
    }
    int help(vector<vector<int>> &grid,int x,int y,int tmp)
    {
        if(x>=grid.size()||y>=grid[0].size())
        {
            return tmp;
        }
        if(grid[x][y]==0||grid[x][y]==2)//不是岛屿或者访问过
        {
            return tmp;
        }
        tmp++;
        grid[x][y]=2;//设置访问标记
        tmp=help(grid,x+1,y,tmp);
        tmp=help(grid,x-1,y,tmp);
        tmp=help(grid,x,y+1,tmp);
        tmp=help(grid,x,y-1,tmp);
        return tmp;
    }
};

发表于 2022-06-27 11:12:55 回复(0)
Java
blue&&lan头像 blue&&lan 
static int c=0;
    public int maxAreaIsland (int[][] grid) {
        int m=0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]==1){
                    dfs(i,j,grid);
                    m=Math.max(m,c);
                    c=0;
                }
            }
        }
        return m;
    }
    void dfs(int x, int y, int[][] grid){
        if(x<0 || y<0 || x>=grid.length || y>=grid[0].length)return;
        if(grid[x][y]==0)return;
        c++;
        grid[x][y]=0;
        dfs(x+1,y,grid);
        dfs(x,y+1,grid);
        dfs(x,y-1,grid);
        dfs(x-1,y,grid);
    }

发表于 2022-06-02 19:19:02 回复(0)
the幻云头像 the幻云 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    //dfs
    int dx[4]={0,0,-1,1};
    int dy[4]={-1,1,0,0};
    int cnt;
    int res=0;
    
    void dfs(int i,int j,vector<vector<int>>& grid,vector<vector<int>>& vis)
    {
        vis[i][j]=1;
        cnt++;
        for(int k=0;k<4;k++)
        {
            int ni=i+dx[k],nj=j+dy[k];
            if(ni>=0&&ni<grid.size()&&nj>=0&&nj<grid[0].size()&&grid[ni][nj]==1&&vis[ni][nj]==0)
                dfs(ni,nj,grid,vis);
        }
        return;
    }  
    int maxAreaIsland(vector<vector<int> >& grid) {
        // write code here
        int m=grid.size();
        int n=grid[0].size();
        vector<vector<int>> vis(m,vector<int>(n,0));
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1&&vis[i][j]==0)
                {
                    cnt=0;
                    dfs(i,j,grid,vis);
                    res=max(res,cnt);
                }
            }
        }
        return res;
    }
};

发表于 2022-04-15 15:53:24 回复(0)
Go
王飞-6头像 王飞-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)
提交观点

问题信息

递归
难度：
11条回答 1970浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号