99. 计数孤岛
题目描述
给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。
输入描述
第一行包含两个整数 N, M，表示矩阵的行数和列数。
后续 N 行，每行包含 M 个数字，数字为 1 或者 0。
输出描述
输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。
输入示例
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
输出示例
3
提示信息
根据测试案例中所展示，岛屿数量共有 3 个，所以输出 3。
数据范围：
1 <= N, M <= 50
解题思路
深搜版
import java.util.*;
class Main {
public static final int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public static void dfs(int[][] martix, boolean[][] visited, int x, int y) {
for (int i = 0; i < 4; i++) {
int nextX = x + dir[i][0];
int nextY = y + dir[i][1];
if (nextX < 0 || nextY < 0 || nextX >= martix.length || nextY >= martix[0].length) {
continue;
}
if (!visited[nextX][nextY] && martix[nextX][nextY] == 1) {
visited[nextX][nextY] = true;
dfs(martix, visited, nextX, nextY);
}
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt();
int[][] martix = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
martix[i][j] = in.nextInt();
}
}
in.close();
boolean[][] visited = new boolean[n][m];
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && martix[i][j] == 1) {
ans++;
dfs(martix, visited, i, j);
}
}
}
System.out.println(ans);
}
}
广搜版
public static void bfs(int[][] martix, boolean[][] visited, int x, int y) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{x, y});
visited[x][y] = true;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int curX = cur[0];
int curY = cur[1];
for (int i = 0; i < 4; i++) {
int nextX = curX + dir[i][0];
int nextY = curY + dir[i][1];
if (nextX < 0 || nextX >= martix.length || nextY < 0 || nextY >= martix[0].length) {
continue;
}
if (!visited[nextX][nextY] && martix[nextX][nextY] == 1) {
queue.add(new int[]{nextX, nextY});
visited[nextX][nextY] = true;
}
}
}
}
100.最大岛屿的面积
题目描述
给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。
输入描述
第一行包含两个整数 N, M，表示矩阵的行数和列数。后续 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。
输出描述
输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。
输入示例
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
输出示例
4
提示信息
样例输入中，岛屿的最大面积为 4。
数据范围：
1 <= M, N <= 50。
解题思路
import java.util.*;
class Main {
public static int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public static int area = 0;
public static void dfs(int[][] martix, boolean[][] visited, int x, int y) {
area++;
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nextX = x + dir[i][0];
int nextY = y + dir[i][1];
if (nextX < 0 || nextX >= martix.length
|| nextY < 0 || nextY >= martix[0].length) {
continue;
}
if (!visited[nextX][nextY] && martix[nextX][nextY] == 1) {
dfs(martix, visited, nextX, nextY);
}
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt();
int[][] martix = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
martix[i][j] = in.nextInt();
}
}
in.close();
int ans = 0;
boolean[][] visited = new boolean[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && martix[i][j] == 1) {
area = 0;
dfs(martix, visited, i, j);
ans = Math.max(area, ans);
}
}
}
System.out.println(ans);
}
}
评论