做的网站打开显示无标题,一张图片网站代码,新产品推广方案范文,做网站一般注册哪几类商标语言
Java
99.岛屿数量 深搜 广搜
99. 岛屿数量
题目
题目描述
给定一个由 1#xff08;陆地#xff09;和 0#xff08;水#xff09;组成的矩阵#xff0c;你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成#xff0c;并且四周都是水域。你可…语言
Java
99.岛屿数量 深搜 广搜
99. 岛屿数量
题目
题目描述
给定一个由 1陆地和 0水组成的矩阵你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成并且四周都是水域。你可以假设矩阵外均被水包围。
输入描述
第一行包含两个整数 N, M表示矩阵的行数和列数。
后续 N 行每行包含 M 个数字数字为 1 或者 0。
输出描述
输出一个整数表示岛屿的数量。如果不存在岛屿则输出 0。 思路深搜版本
第一次思路
1.创建一个二维数组 2.通过Scanner输入多少就是几乘几的二维数组定义一个结果res
3.这时我们得到一个二维数组遍历二维数组找到为1的地方
4.如何看他周围有没有1组成个大岛屿 5.如果是大岛屿res1
6.输出res的值
最终思路
初始化 读取网格的大小行数和列数。创建一个与网格大小相同的二维数组grid来存储输入数据。创建一个同样大小的二维布尔数组visited用于跟踪哪些陆地1已经被访问过。初始时所有位置都设为false。遍历网格 使用两层嵌套循环遍历网格中的每一个位置。对于每个位置检查它是否是陆地grid[i][j] 1且尚未被访问visited[i][j] false。深度优先搜索DFS 如果发现一个未被访问的陆地那么我们就找到了一个新的岛屿。此时将岛屿计数器加一。对这个陆地位置执行DFS以标记与这个陆地相连的所有陆地即这个岛屿的所有部分为已访问。DFS过程中我们遍历当前陆地位置的四个相邻方向上、下、左、右如果相邻位置是陆地且未被访问则递归地对该位置执行DFS。结果输出 遍历和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代表陆地组成的连通区域的数量。初始化 创建一个与网格大小相同的visited数组或类似的数据结构用于跟踪哪些位置已经被访问过。创建一个队列如LinkedList用于BFS的遍历。遍历网格 遍历网格的每个位置。对于每个位置如果它是陆地即值为1且尚未被访问过则将其视为一个新的连通区域。BFS遍历 将当前位置加入队列并标记为已访问。当队列不为空时从队列中取出一个位置并检查其四个相邻位置上、下、左、右。如果相邻位置是陆地且未被访问过则将其加入队列并标记为已访问。重复此过程直到队列为空。计数 对于每个新发现的连通区域增加计数器。输出结果 遍历结束后输出连通区域的数量。
代码
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) { Queueint[] 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); }
}
易错点
边界检查 在检查相邻位置时容易忘记检查它们是否越界即是否在网格的范围内。重复访问 如果没有正确地使用visited数组或类似的数据结构可能会导致同一个位置被多次访问从而影响结果。
100.岛屿的最大面积
100. 岛屿的最大面积
题目
题目描述
给定一个由 1陆地和 0水组成的矩阵计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成并且四周都是水域。你可以假设矩阵外均被水包围。
输入描述
第一行包含两个整数 N, M表示矩阵的行数和列数。后续 N 行每行包含 M 个数字数字为 1 或者 0表示岛屿的单元格。
输出描述
输出一个整数表示岛屿的最大面积。如果不存在岛屿则输出 0。
思路 输入读取 读取网格的行数n和列数m。读取网格的数据存储在二维数组grid中。 初始化 初始化一个与grid大小相同的二维布尔数组visited用于标记每个位置是否被访问过。 遍历网格 遍历整个网格对于每个未访问的陆地即grid[i][j] 1且!visited[i][j]执行以下操作 初始化count为1表示当前岛屿的大小。标记当前位置为已访问。调用DFS函数遍历并标记所有相邻的陆地。更新最大岛屿大小result。 DFS函数 从当前位置(x, y)出发遍历四个方向的相邻位置。如果相邻位置越界或不是陆地或已经访问过则跳过。否则标记该位置为已访问增加count并递归调用DFS函数。 输出结果 输出最大的岛屿大小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函数中需要检查下一个位置是否越界。如果越界直接跳过。 示例代码中已经包含了越界检查
总结
今天了解深搜和广搜的思路做了模板题岛屿问题。
明天继续加油
道阻且长行则将至。
