Day45 | 99.岛屿数量 深搜 广搜 100.岛屿的最大面积

语言

Java

99.岛屿数量 深搜 广搜

99. 岛屿数量

题目

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。

后续 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述

输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。

思路（深搜版本）

第一次思路

1.创建一个二维数组
2.通过Scanner输入多少就是几乘几的二维数组，定义一个结果res

3.这时我们得到一个二维数组，遍历二维数组，找到为1的地方

4.？如何看他周围有没有1组成个大岛屿
5.如果是大岛屿res+1

6.输出res的值

最终思路

1. 初始化：
   • 读取网格的大小（行数和列数）。
   • 创建一个与网格大小相同的二维数组grid来存储输入数据。
   • 创建一个同样大小的二维布尔数组visited，用于跟踪哪些陆地（1）已经被访问过。初始时，所有位置都设为false。
2. 遍历网格：
   • 使用两层嵌套循环遍历网格中的每一个位置。
   • 对于每个位置，检查它是否是陆地（grid[i][j] == 1）且尚未被访问（visited[i][j] == false）。
3. 深度优先搜索（DFS）：
   • 如果发现一个未被访问的陆地，那么我们就找到了一个新的岛屿。此时，将岛屿计数器加一。
   • 对这个陆地位置执行DFS，以标记与这个陆地相连的所有陆地（即这个岛屿的所有部分）为已访问。
   • DFS过程中，我们遍历当前陆地位置的四个相邻方向（上、下、左、右），如果相邻位置是陆地且未被访问，则递归地对该位置执行DFS。
4. 结果输出：
   • 遍历和DFS完成后，岛屿计数器的值即为网格中岛屿的总数。
   • 输出岛屿的总数。

代码

import java.util.Scanner;  public class Main {  static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四个方向  static void dfs(int[][] grid, 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 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;  // 越界了，直接跳过  if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 没有访问过的 同时 是陆地的  visited[nextx][nexty] = true;  dfs(grid, visited, nextx, nexty);  }  }  }  public static void main(String[] args) {  Scanner scanner = new Scanner(System.in);  int n = scanner.nextInt();  int m = scanner.nextInt();  int[][] grid = new int[n][m];  boolean[][] visited = new boolean[n][m];  for (int i = 0; i < n; i++) {  for (int j = 0; j < m; j++) {  grid[i][j] = scanner.nextInt();  }  }  int result = 0;  for (int i = 0; i < n; i++) {  for (int j = 0; j < m; j++) {  if (!visited[i][j] && grid[i][j] == 1) {  visited[i][j] = true;  result++; // 遇到没访问过的陆地，+1  dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true  }  }  }  System.out.println(result);  }  
}

易错点

• DFS：深度优先搜索是解决此类问题的关键。它允许我们从一个陆地位置开始，探索并标记与该位置相连的所有陆地，直到没有更多的相邻陆地为止。
• 避免重复计数：通过visited数组，我们可以确保每个岛屿只被计数一次。即使一个岛屿由多个陆地组成，DFS也会确保我们只在首次遇到岛屿时增加计数器，并标记岛屿的所有部分为已访问。
• 边界条件：在DFS过程中，我们需要检查相邻位置是否越界（即是否仍在网格范围内内），以及相邻位置是否是陆地且未被访问

思路（广搜版本）

1. 理解问题：
   • 首先，明确问题的要求。例如，在网格中，你可能需要计算由1（代表陆地）组成的连通区域的数量。
2. 初始化：
   • 创建一个与网格大小相同的visited数组（或类似的数据结构），用于跟踪哪些位置已经被访问过。
   • 创建一个队列（如LinkedList），用于BFS的遍历。
3. 遍历网格：
   • 遍历网格的每个位置。
   • 对于每个位置，如果它是陆地（即值为1）且尚未被访问过，则将其视为一个新的连通区域。
4. BFS遍历：
   • 将当前位置加入队列，并标记为已访问。
   • 当队列不为空时，从队列中取出一个位置，并检查其四个相邻位置（上、下、左、右）。
   • 如果相邻位置是陆地且未被访问过，则将其加入队列并标记为已访问。
   • 重复此过程，直到队列为空。
5. 计数：
   • 对于每个新发现的连通区域，增加计数器。
6. 输出结果：
   • 遍历结束后，输出连通区域的数量。

代码

import java.util.LinkedList;  
import java.util.Queue;  
import java.util.Scanner;  
import java.util.Vector;  public class Main {  private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四个方向  public static void bfs(int[][] grid, boolean[][] visited, int x, int y) {  Queue<int[]> que = new LinkedList<>();  que.offer(new int[]{x, y});  visited[x][y] = true; // 只要加入队列，立刻标记  while (!que.isEmpty()) {  int[] cur = que.poll();  int curx = cur[0];  int cury = cur[1];  for (int i = 0; i < 4; i++) {  int nextx = curx + DIRECTIONS[i][0];  int nexty = cury + DIRECTIONS[i][1];  if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue; // 越界了，直接跳过  if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {  que.offer(new int[]{nextx, nexty});  visited[nextx][nexty] = true; // 只要加入队列立刻标记  }  }  }  }  public static void main(String[] args) {  Scanner scanner = new Scanner(System.in);  int n = scanner.nextInt();  int m = scanner.nextInt();  int[][] grid = new int[n][m];  boolean[][] visited = new boolean[n][m];  for (int i = 0; i < n; i++) {  for (int j = 0; j < m; j++) {  grid[i][j] = scanner.nextInt();  }  }  int result = 0;  for (int i = 0; i < n; i++) {  for (int j = 0; j < m; j++) {  if (!visited[i][j] && grid[i][j] == 1) {  result++; // 遇到没访问过的陆地，+1  bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true  }  }  }  System.out.println(result);  }  
}

易错点

1. 边界检查：
   • 在检查相邻位置时，容易忘记检查它们是否越界（即是否在网格的范围内）。
2. 重复访问：
   • 如果没有正确地使用visited数组（或类似的数据结构），可能会导致同一个位置被多次访问，从而影响结果。

100.岛屿的最大面积

100. 岛屿的最大面积

题目

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。后续 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。

思路

1. 输入读取：

   • 读取网格的行数n和列数m。
   • 读取网格的数据，存储在二维数组grid中。

2. 初始化：

   • 初始化一个与grid大小相同的二维布尔数组visited，用于标记每个位置是否被访问过。

3. 遍历网格：

   • 遍历整个网格，对于每个未访问的陆地（即grid[i][j] == 1且!visited[i][j]），执行以下操作：
     • 初始化count为1，表示当前岛屿的大小。
     • 标记当前位置为已访问。
     • 调用DFS函数，遍历并标记所有相邻的陆地。
     • 更新最大岛屿大小result。

4. DFS函数：

   • 从当前位置(x, y)出发，遍历四个方向的相邻位置。
   • 如果相邻位置越界或不是陆地或已经访问过，则跳过。
   • 否则，标记该位置为已访问，增加count，并递归调用DFS函数。

5. 输出结果：

   • 输出最大的岛屿大小result。

代码

import java.util.Scanner;public class Main {private static int count;private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四个方向public static void dfs(int[][] grid, 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 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;  // 越界了，直接跳过if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 没有访问过的 同时 是陆地的visited[nextx][nexty] = true;count++;dfs(grid, visited, nextx, nexty);}}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[][] grid = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = scanner.nextInt();}}boolean[][] visited = new boolean[n][m];int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == 1) {count = 1;  // 因为dfs处理下一个节点，所以这里遇到陆地了就先计数，dfs处理接下来的相邻陆地visited[i][j] = true;dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 trueresult = Math.max(result, count);}}}System.out.println(result);}
}

易错点

数组越界：

在DFS函数中，需要检查下一个位置是否越界。如果越界，直接跳过。
示例代码中已经包含了越界检查：

总结

今天了解深搜和广搜的思路，做了模板题岛屿问题。

明天继续加油！

道阻且长，行则将至。