最大岛屿体积,图的用法

发布时间 2023-07-16 21:56:58作者: sgj191024
public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num1 = scanner.nextInt();
        int num2 = scanner.nextInt();
        int[][] arr = new int[num1][num2];
        while (scanner.hasNext()){
            for (int i = 0; i < num1; i++) {
                for (int j = 0; j < num2; j++) {
                    arr[i][j] = scanner.nextInt();
                }
            }
            int max = 0;
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr[i].length; j++) {
                    if(arr[i][j] > 0){
                        int val = dfs(i,j,arr);
                        max = Math.max(max,val);
                    }
                }
            }
            System.out.println(max);
        }

    }

    private static int dfs(int i, int j,int[][] arr) {
        int res =0;
        if(i < 0 || i >= arr.length || j < 0 || j >= arr[0].length || arr[i][j] == 0){
            return 0;
        }
        res += arr[i][j];
        arr[i][j] = 0;
        res += dfs(i-1,j,arr);
        res +=dfs(i+1,j,arr);
        res +=dfs(i,j+1,arr);
        res +=dfs(i,j-1,arr);
        return res;

    }

  

最大岛屿体积

题目描述

给你一个由 大于0的数(陆地)和 0(水)组成的的二维网格,请你计算网格中最大岛屿的体积。陆地的数表示所在岛屿的体积。

岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。

 

  总结:找到一个大于0的岛,把它的体积累计到总和上,然后把他置为0,然后把他上下左右的也这样处理,并递归,这样就把这一片岛屿体积求出来了,然后比较最大值。