【华为OD题库-097】最大岛屿体积-java

题目

题目描述
给你一个由大于0的数（陆地)和0(水)组成的的二维网格，请你计算网格中最大岛屿的体积。陆地的数表示所在岛屿的体积。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
输入描述
第一行是二维网格的宽和高。后面几行是二维网格。
输出描述
输出岛屿的最大体积。
样例
输入
5 5
0 1 1 0 0
0 1 1 0 0
0 0 0 0 0
0 0 1 2 3
0 0 1 3 9
输出
19

思路

dfs递归处理即可得到每个岛屿的体积，最后返回最大体积即可

题解

package hwod;

import java.util.Scanner;

public class MaxIslandVolume {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] grids = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grids[i][j] = sc.nextInt();
            }
        }
        System.out.println(maxIslandVolume(grids));
    }

    private static int[] x_axis = new int[]{1, 0, -1, 0};
    private static int[] y_axis = new int[]{0, 1, 0, -1};

    private static int area;

    private static int maxIslandVolume(int[][] grids) {
        int res = Integer.MIN_VALUE;
        int m = grids.length;
        if (m == 0) return 0;
        int n = grids[0].length;
        int[] used = new int[m * n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grids[i][j] != 0 && used[i * n + j] == 0) {
                    area = 0;
                    recur(grids, i, j, used);
                    res = Math.max(area, res);
                }
            }
        }
        return res;
    }

    private static void recur(int[][] grids, int i, int j, int[] used) {
        int m = grids.length, n = grids[0].length;
        area += grids[i][j];
        used[i * n + j] = 1;
        for (int k = 0; k < 4; k++) {
            int nx = i + x_axis[k];
            int ny = j + y_axis[k];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && used[nx * n + ny] != 1 && grids[nx][ny] != 0) {
                recur(grids, nx, ny, used);
            }
        }
    }
}

推荐

如果你对本系列的其他题目感兴趣，可以参考华为OD机试真题及题解（JAVA），查看当前专栏更新的所有题目。