一、实战
99岛屿数量 深搜
本题中每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成，也就是说斜角度链接是不算的。思路是用遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。在遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。
深度优先搜索有两个版本，一个是没有终止条件，一个是有终止条件
没有终止条件版本：
package org.example;//具体运行时去掉
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int m = scan.nextInt(); // 网格行数
int n = scan.nextInt(); // 网格列数
int[][] grid = new int[m][n]; // 存储网格数据
// 输入网格
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
grid[i][j] = scan.nextInt();
}
}
boolean[][] visited = new boolean[m][n]; // 标记是否已访问
int result = 0; // 记录岛屿数量
// 遍历每个格子
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 如果当前格子是陆地（1）且未被访问
if (!visited[i][j] && grid[i][j] == 1) {
result++; // 发现新岛屿
visited[i][j] = true; // 标记为已访问
dfs(visited, i, j, grid); // 深度优先搜索，标记整个连通区域
}
}
}
System.out.println(result); // 输出岛屿总数
scan.close();
}
// 四个方向：右、下、上、左（x, y 增量）
public static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
/**
* 从坐标 (x, y) 开始进行深度优先搜索，标记所有相连的陆地
*/
private static void dfs(boolean[][] visited, int x, int y, int[][] grid) {
// 向四个方向扩展
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 >= grid.length || nextY >= grid[0].length) {
continue;
}
// 如果下一个位置是未访问的陆地
if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {
visited[nextX][nextY] = true; // 标记为已访问
dfs(visited, nextX, nextY, grid); // 继续递归搜索
}
}
}
}有终止条件版本，其实终止条件 就写在了 调用dfs的地方，如果遇到不合法的方向，直接不会去调用dfs。：
package org.example;//具体运行时去掉
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int m = scan.nextInt(); // 网格行数
int n = scan.nextInt(); // 网格列数
int[][] grid = new int[m][n]; // 存储网格数据
// 输入网格
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
grid[i][j] = scan.nextInt();
}
}
boolean[][] visited = new boolean[m][n]; // 标记是否已访问
int result = 0; // 记录岛屿数量
// 遍历每个格子
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 如果当前格子是陆地（1）且未被访问
if (!visited[i][j] && grid[i][j] == 1) {
result++; // 发现新岛屿
visited[i][j] = true; // 标记为已访问
dfs(visited, i, j, grid); // 深度优先搜索，标记整个连通区域
}
}
}
System.out.println(result); // 输出岛屿总数
scan.close();
}
// 四个方向：右、下、上、左（x, y 增量）
public static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
/**
* 从坐标 (x, y) 开始进行深度优先搜索，标记所有相连的陆地
*/
private static void dfs(boolean[][] visited, int x, int y, int[][] grid) {
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];
int nextY = y + dir[i][1];
// 越界检查
if (nextX < 0 || nextY < 0 || nextX >= grid.length || nextY >= grid[0].length) {
continue;
}
dfs(visited, nextX, nextY, grid); // 继续递归搜索
}
}
}99岛屿数量 广搜
本题思路与深搜类似，遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。再遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。
用广搜做这道题目的时候容易超时，因为已经入队列的节点因为标记的时间太晚导致重复进入队列，因此只要 加入队列就代表 走过，就需要标记，而不是从队列拿出来的时候再去标记走过。
//超时写法
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
queue<pair<int, int>> que;
que.push({x, y});
// 应在放入队列的时候就进行标记
while(!que.empty()) {
pair<int ,int> cur = que.front(); que.pop();
int curx = cur.first;
int cury = cur.second;
visited[curx][cury] = true; // 从队列中取出在标记走过
for (int i = 0; i < 4; i++) {
int nextx = curx + dir[i][0];
int nexty = cury + dir[i][1];
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界了，直接跳过
if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') {
que.push({nextx, nexty});
}
}
}
}具体代码如下：
package org.example;//具体运行时去掉
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int m = scan.nextInt(); // 网格行数
int n = scan.nextInt(); // 网格列数
int[][] grid = new int[m][n]; // 存储网格数据
// 输入网格
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
grid[i][j] = scan.nextInt();
}
}
boolean[][] visited = new boolean[m][n]; // 标记是否已访问
int result = 0; // 记录岛屿数量
// 遍历每个格子
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 如果当前格子是陆地（1）且未被访问
if (!visited[i][j] && grid[i][j] == 1) {
result++; // 发现新岛屿
visited[i][j] = true; // 标记为已访问
bfs(visited, i, j, grid); // 深度优先搜索，标记整个连通区域
}
}
}
System.out.println(result); // 输出岛屿总数
scan.close();
}
/**
* 自定义 Pair 类，用于封装坐标 (x, y)
*/
static class pair {
int first;
int second;
public pair(int first, int second) {
this.first = first;
this.second = second;
}
}
// 四个方向：右、下、上、左（x, y 增量）
public static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
private static void bfs(boolean[][] visited, int x, int y, int[][] grid) {
Queue<pair> queue = new LinkedList<pair>();//定义坐标队列，没有现成的pair类，在下面自定义了
queue.add(new pair(x, y));
visited[x][y] = true;//遇到入队直接标记为优先，
// 否则出队时才标记的话会导致重复访问，比如下方节点会在右下顺序的时候被第二次访问入队
while (!queue.isEmpty()) {
int curX = queue.peek().first;
int curY = queue.poll().second;//当前横纵坐标
for (int i = 0; i < 4; i++) {
//顺时针遍历新节点next，下面记录坐标
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 pair(nextX, nextY));
visited[nextX][nextY] = true;//逻辑同上
}
}
}
}
/**
* 从坐标 (x, y) 开始进行深度优先搜索，标记所有相连的陆地
*/
private static void dfs(boolean[][] visited, int x, int y, int[][] grid) {
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];
int nextY = y + dir[i][1];
// 越界检查
if (nextX < 0 || nextY < 0 || nextX >= grid.length || nextY >= grid[0].length) {
continue;
}
dfs(visited, nextX, nextY, grid); // 继续递归搜索
}
}
}100岛屿的最大面积（深搜-无结束条件版本）
思路：如果是有结束条件版本，dfs处理当前节点，即在主函数遇到岛屿就计数为0，dfs处理接下来的全部陆地；如果是无结束条件版本，则dfs处理当前节点的相邻节点，即在主函数遇到岛屿就计数为1，dfs处理接下来的相邻陆地
import java.util.*;
import java.math.*;
public class Main {
// 四个方向：右、下、左、上（顺时针）
static final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
static int result = 0; // 记录最大岛屿面积
static int count = 0; // 记录当前岛屿的面积（DFS过程中累加）
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 网格行数
int m = scanner.nextInt(); // 网格列数
int[][] map = new int[n][m]; // 存储地图
// 输入地图数据
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
map[i][j] = scanner.nextInt();
}
}
boolean[][] visited = new boolean[n][m]; // 标记是否已访问
// 遍历每个格子
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 发现未访问的陆地，开始新岛屿的DFS
if (!visited[i][j] && map[i][j] == 1) {
count = 0; // 重置当前岛屿面积计数器
dfs(map, visited, i, j); // 深度优先搜索，统计该岛屿面积
result = Math.max(count, result); // 更新最大面积
}
}
}
System.out.println(result); // 输出最大岛屿面积
scanner.close();
}
/**
* DFS：从 (x, y) 开始遍历整个连通的陆地，累加面积
*/
static void dfs(int[][] map, boolean[][] visited, int x, int y) {
count++; // 当前格子是陆地，面积+1
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 || nextY < 0 ||
nextX >= map.length || nextY >= map[0].length ||
visited[nextX][nextY] || map[nextX][nextY] == 0) {
continue;
}
// 递归访问相邻陆地
dfs(map, visited, nextX, nextY);
}
}
}