第十一章：图论part02
99. 岛屿数量 深搜
注意深搜的两种写法，熟练掌握这两种写法 以及 知道区别在哪里，才算掌握的深搜。
文章讲解
思路
- 遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。
// 终止条件在调用dfs的地方
import java.util.Scanner;
class Main{
// 定义四个方向的二维数组，表示上下左右四个方向的坐标变化
private static final int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] grid = new int[n][m];
// 读取网格数据
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
grid[i][j] = sc.nextInt();
}
}
// 创建访问标记数组，初始化为false
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){
visited[i][j] = true; // 标记为已访问
result++;
dfs(grid, visited, i, j);
}
}
}
System.out.println(result);
}
private static void dfs(int[][] grid, boolean[][] visited, int x, int y){
// 遍历四个方向
for(int i = 0; i < 4; i++){
//计算下一个位置的x坐标
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
// 检查是否越界
// grid[0].length 表示二维数组中每一行的列数（即网格的宽度）。
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); // 递归调用，继续搜索
}
}
}
}
关于坐标
int nextx = x + dir[i][0]; 这一行代码的意思是计算下一个位置的 x 坐标。为了更好地理解这个表达式，我们需要了解上下文和相关变量的定义。
在这个代码中，dir 是一个二维数组，用于表示四个方向（上、右、下、左）的坐标变化。具体定义如下：
private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
-
dir[0]表示向右移动，坐标变化为(0, 1)。 -
dir[1]表示向下移动，坐标变化为(1, 0)。 -
dir[2]表示向上移动，坐标变化为(-1, 0)。 -
dir[3]表示向左移动，坐标变化为(0, -1)。
具体到数组元素：
dir[0] = {0, 1}：表示向右移动
dir[0][0] = 0：x 坐标不变
dir[0][1] = 1：y 坐标增加 1
dir[1] = {1, 0}：表示向下移动
dir[1][0] = 1：x 坐标增加 1
dir[1][1] = 0：y 坐标不变
dir[2] = {-1, 0}：表示向上移动
dir[2][0] = -1：x 坐标减少 1
dir[2][1] = 0：y 坐标不变
dir[3] = {0, -1}：表示向左移动
dir[3][0] = 0：x 坐标不变
dir[3][1] = -1：y 坐标减少 1
二维数组（如在图像处理中）通常采用以下约定：
x 轴表示行（row），y 轴表示列（column）。
(0, 0) 表示左上角的元素。
x 坐标增加表示向下移动。
y 坐标增加表示向右移动。
为了进一步解释，我们来看看一个二维数组的表示方式：
(0,0) (0,1) (0,2) ...
(1,0) (1,1) (1,2) ...
(2,0) (2,1) (2,2) ...
在这个坐标系统中：
向右移动是 y 坐标增加，即 (0, 0) -> (0, 1)。
向下移动是 x 坐标增加，即 (0, 0) -> (1, 0)。
向上移动是 x 坐标减少，即 (1, 0) -> (0, 0)。
向左移动是 y 坐标减少，即 (0, 1) -> (0, 0)。
图示说明
假设我们有一个二维网格，起始点在 (x, y)：
y-1 y y+1
x-1 . . .
x . (x,y) .
x+1 . . .
向右移动：(x, y) -> (x, y + 1)
向下移动：(x, y) -> (x + 1, y)
向上移动：(x, y) -> (x - 1, y)
向左移动：(x, y) -> (x, y - 1)
// 终止条件放在开头
import java.util.Scanner;
class Main {
// 定义四个方向的二维数组，表示上下左右四个方向的坐标变化
private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in); // 创建Scanner对象用于输入
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]; // 创建访问标记数组，初始化为false
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
dfs(grid, visited, i, j); // 深度优先搜索，标记所有相连的陆地
}
}
}
System.out.println(result); // 输出结果，即岛屿数量
}
// 深度优先搜索函数
private static void dfs(int[][] grid, boolean[][] visited, int x, int y) {
// 终止条件：访问过的节点 或者 遇到海水
if (visited[x][y] || grid[x][y] == 0) return;
visited[x][y] = true; // 标记访问过
// 遍历四个方向
for (int i = 0; i < 4; i++) {
int nextx = x + dir[i][0]; // 计算下一个位置的x坐标
int nexty = y + dir[i][1]; // 计算下一个位置的y坐标
// 检查是否越界
if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;
dfs(grid, visited, nextx, nexty); // 递归调用，继续搜索
}
}
}
Java还是老老实实写这个版本吧。。。
99. 岛屿数量 广搜
注意广搜的两种写法，第一种写法为什么会超时。
文章讲解
思路
- bfs要注意的点：超时根本原因是只要 加入队列就代表 走过，就需要标记，而不是从队列拿出来的时候再去标记走过。
// bfs
import java.util.*;
class Main {
// 定义四个方向的二维数组，表示上下左右四个方向的坐标变化
private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in); // 创建Scanner对象用于输入
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]; // 创建访问标记数组，初始化为false
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); // 深度优先搜索，标记所有相连的陆地
}
}
}
System.out.println(result); // 输出结果，即岛屿数量
}
// 广度优先搜索函数
private static void bfs(int[][] grid, 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 >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;
// 如果未访问且是陆地
if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {
queue.add(new int[]{nextx, nexty}); // 将新位置加入队列
visited[nextx][nexty] = true; // 只要加入队列，立刻标记为已访问
}
}
}
}
}
100. 岛屿的最大面积
本题就是基础题了，做过上面的题目，本题很快。
文章讲解
dfs的两种写法
版本一
在主函数中遇到岛屿时计数为1，dfs处理接下来的相邻陆地：
import java.util.Scanner;
public class Main {
static int count;
static 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); // 将与其链接的陆地都标记上 true
result = Math.max(result, count);
}
}
}
System.out.println(result);
}
}
版本二
在主函数中遇到岛屿时计数为0，dfs处理接下来的全部陆地：
import java.util.Scanner;
public class Main {
static int count;
static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四个方向
public static void dfs(int[][] grid, boolean[][] visited, int x, int y) {
if (visited[x][y] || grid[x][y] == 0) return; // 终止条件：访问过的节点 或者 遇到海水
visited[x][y] = true; // 标记访问过
count++;
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; // 越界了，直接跳过
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 = 0; // 因为dfs处理当前节点，所以遇到陆地计数为0，进dfs之后在开始从1计数
dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
result = Math.max(result, count);
}
}
}
System.out.println(result);
}
}
bfs
import java.util.*;
public class Main {
static int count = 0;
static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四个方向
// 广度优先搜索 (BFS) 方法，用于探索一个岛屿并统计其面积
public static void bfs(int[][] grid, boolean[][] visited, int x, int y) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y}); // 将初始坐标加入队列
visited[x][y] = true; // 标记初始坐标已访问
count++; // 增加岛屿面积计数
// 当队列不为空时，持续处理
while (!queue.isEmpty()) {
int[] current = queue.poll(); // 获取并移除队列头部的元素
int xx = current[0]; // 当前处理的 x 坐标
int yy = current[1]; // 当前处理的 y 坐标
// 遍历四个方向
for (int i = 0; i < 4; i++) {
int nextx = xx + dir[i][0]; // 计算下一个 x 坐标
int nexty = yy + dir[i][1]; // 计算下一个 y 坐标
// 检查下一个坐标是否越界
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++; // 增加岛屿面积计数
queue.offer(new int[]{nextx, nexty}); // 将下一个坐标加入队列
}
}
}
}
// 主方法，用于计算网格中岛屿的最大面积
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] grid = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = sc.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 = 0;
bfs(grid, visited, i, j);
result = Math.max(result, count);
}
}
}
System.out.println(result);
}
}
注意越界条件是大于等于
