【华为OD题库-097】最大岛屿体积-java
2023-12-20 08:21:06
题目
题目描述
给你一个由大于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),查看当前专栏更新的所有题目。
文章来源:https://blog.csdn.net/qq_31076523/article/details/135079940
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!