笔记
在涉及二维表中，无论是深搜和广搜，都是定义了一个isUsed数组来标记哪一些元素已经被访问过了，重要的解题思路其实是遍历的条件。
比如孤岛的总面积这一题，判断孤岛就要判断岛屿是否与边界接壤。
101. 孤岛的总面积
dfs深搜
模板-所有可达路径
邻接表法，就记一个邻接表
98. 所有可达路径
import java.util.*;public class Main {// 存储当前路径static List<Integer> path = new ArrayList<>();// 存储所有找到的路径static List<List<Integer>> ret = new ArrayList<>();public static void main(String[] args) {// 创建Scanner对象来读取用户输入Scanner input = new Scanner(System.in);// 读取顶点数和边数int n = input.nextInt();int m = input.nextInt();// 创建邻接表来表示图，大小为n+1因为顶点编号从1开始List<List<Integer>> map = new ArrayList<>(m + 1);for (int i = 0; i <= n; i++) {map.add(new ArrayList<>());}// 读取边的信息，并添加到邻接表中for (int i = 0; i < m; i++) {int s = input.nextInt(); // 边的起始顶点int t = input.nextInt(); // 边的终止顶点map.get(s).add(t); // 将终止顶点添加到起始顶点的邻接列表中}// 将起点（1号顶点）添加到当前路径中，并开始深度优先搜索path.add(1);dfs(map, 1, n);// 检查是否找到了路径if (ret.isEmpty()) {System.out.println(-1); // 如果没有找到路径，输出-1} else {// 输出所有找到的路径for (List<Integer> list : ret) {for (int i = 0; i < list.size() - 1; i++) {System.out.print(list.get(i) + " ");}System.out.println(list.get(list.size() - 1));}}}// 深度优先搜索方法static void dfs(List<List<Integer>> map, int i, int n) {// 如果当前顶点是终点，则将当前路径添加到结果中if (i == n) {ret.add(new ArrayList<>(path));return;}// 遍历当前顶点的所有邻接顶点for (int temp : map.get(i)) {// 将邻接顶点添加到当前路径中path.add(temp);// 递归地对邻接顶点进行深度优先搜索dfs(map, temp, n);// 回溯，从当前路径中移除最后一个顶点path.remove(path.size() - 1);}}
}岛屿数量（深搜版）
99. 岛屿数量
import java.util.*;// 主类
public class Main {// 定义一个静态变量result，用于记录连通区域的数量static int result = 0;// 定义一个二维数组dir，表示四个方向（上、右、下、左）的移动static int dir[][] = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 深度优先搜索（DFS）方法，用于遍历地图上的连通区域static void dfs(int[][] map, boolean[][] isUsed, int x, int y) {// 遍历四个方向for(int i = 0 ; i < 4 ; i++ ){// 计算下一个位置的坐标int nextX = x + dir[i][0];int nextY = y + dir[i][1];// 检查下一个位置是否在地图范围内，并且没有被访问过，以及该位置是否为1（即可以访问）if(nextX >= 0 && nextX < map.length &&nextY >= 0 && nextY < map[0].length &&isUsed[nextX][nextY] == false &&map[nextX][nextY] == 1){// 标记下一个位置为已访问isUsed[nextX][nextY] = true;// 递归调用DFS方法，继续遍历下一个连通区域dfs(map, isUsed, nextX, nextY);}}}// 主方法public static void main (String[] args) {// 创建一个Scanner对象，用于读取用户输入Scanner input = new Scanner(System.in);// 读取地图的行数和列数int n = input.nextInt();int m = input.nextInt();// 创建一个二维数组map，用于存储地图信息，1表示可以访问，0表示不可以访问int map[][] = new int[n][m];// 读取地图的具体信息for(int i = 0 ; i < n; i++){for(int j = 0 ; j < m; j++){map[i][j] = input.nextInt();}}// 创建一个二维数组isUsed，用于标记地图上的位置是否已经被访问过boolean isUsed[][] = new boolean[n][m];// 遍历地图，找出所有未访问的1（可以访问的位置），并使用DFS方法遍历连通区域for(int i = 0 ; i < n; i++){for(int j = 0 ; j < m; j++){// 如果当前位置没有被访问过，并且该位置为1if(isUsed[i][j] == false && map[i][j] == 1){// 标记当前位置为已访问isUsed[i][j] = true;// 连通区域的数量加1result++;// 调用DFS方法，从当前位置开始遍历连通区域dfs(map, isUsed, i, j);}}}// 输出连通区域的数量System.out.println(result);}
}岛屿的最大面积（深搜版）
100. 岛屿的最大面积
import java.util.*;// 主类
public class Main {// 定义两个静态变量，分别用于记录找到的最大连通区域的大小和当前连通区域的大小static int maxSize = 0;static int localSize = 0;// 定义一个二维数组dir，表示四个方向（右、下、左、上）的移动static int dir[][] = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 深度优先搜索（DFS）方法，用于遍历地图上的连通区域static void dfs(int[][] map, boolean[][] isUsed, int x, int y) {// 遍历四个方向for(int i = 0 ; i < 4; i++){// 计算下一个位置的坐标int nextX = x + dir[i][0];int nextY = y + dir[i][1];// 检查下一个位置是否在地图范围内，并且没有被访问过，以及该位置是否为1（即可以访问）if(nextX >= 0 && nextX < map.length &&nextY >= 0 && nextY < map[0].length &&isUsed[nextX][nextY] == false &&map[nextX][nextY] == 1){// 如果条件满足，将当前位置加入到连通区域中localSize++;// 标记下一个位置为已访问isUsed[nextX][nextY] = true;// 递归调用DFS方法，继续遍历下一个连通区域dfs(map, isUsed, nextX, nextY);}}}// 主方法public static void main (String[] args) {// 创建一个Scanner对象，用于读取用户输入Scanner sc = new Scanner(System.in);// 读取地图的行数和列数int m = sc.nextInt();int n = sc.nextInt();// 创建一个二维数组map，用于存储地图信息，1表示可以访问，0表示不可以访问int[][] map = new int[m][n];// 创建一个二维数组isUsed，用于标记地图上的位置是否已经被访问过boolean[][] isUsed = new boolean[m][n];// 读取地图的具体信息for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {map[i][j] = sc.nextInt();}}// 遍历地图，找出所有未访问的1（可以访问的位置），并使用DFS方法遍历连通区域for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 如果当前位置没有被访问过，并且该位置为1if(isUsed[i][j] == false && map[i][j] == 1){// 标记当前位置为已访问isUsed[i][j] = true;// 初始化当前连通区域的大小为1（当前位置）localSize = 1;// 调用DFS方法，从当前位置开始遍历连通区域dfs(map, isUsed, i, j);// 更新最大连通区域的大小maxSize = Math.max(maxSize, localSize);}}}// 输出最大连通区域的大小System.out.println(maxSize);}
}孤岛的总面积（深搜版）
边界问题
101. 孤岛的总面积
import java.util.*;public class Main {// 用于记录找到的岛屿的总面积static int size = 0;// 用于表示四个基本方向：右、下、左、上// 每个方向用一个包含两个整数的数组表示，第一个整数表示x轴（行）的变化，第二个整数表示y轴（列）的变化static int dir[][] = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 深度优先搜索（DFS）方法，用于遍历岛屿并计算面积// map：表示地图的二维数组，其中的元素1表示岛屿，0表示水域// x：当前位置的x坐标（行）// y：当前位置的y坐标（列）static void dfs(int map[][], int x, int y) {// 将当前位置标记为已访问（0），避免重复计算map[x][y] = 0;// 增加岛屿的面积计数size++;// 遍历四个方向for (int i = 0; i < 4; i++) {// 计算下一个位置的坐标int nextX = x + dir[i][0];int nextY = y + dir[i][1];// 检查下一个位置是否在地图范围内，并且是否是未访问的岛屿if (nextX >= 0 && nextX < map.length && // 检查x坐标是否在范围内nextY >= 0 && nextY < map[0].length && // 检查y坐标是否在范围内map[nextX][nextY] == 1) { // 检查该位置是否是岛屿（值为1）// 如果是未访问的岛屿，递归调用dfs方法dfs(map, nextX, nextY);}}}public static void main(String[] args) {// 创建Scanner对象用于读取用户输入Scanner input = new Scanner(System.in);// 读取地图的行数和列数int n = input.nextInt();int m = input.nextInt();// 根据输入的行数和列数创建二维数组mapint map[][] = new int[n][m];// 读取地图的具体数据，1表示岛屿，0表示水域for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {map[i][j] = input.nextInt();}}// 遍历地图的边界，寻找岛屿并进行深度优先搜索// 首先检查上边界和下边界for (int i = 0; i < n; i++) {if (map[i][0] == 1) {// 如果在上边界找到岛屿，调用dfs方法dfs(map, i, 0);}if (map[i][m - 1] == 1) {// 如果在下边界找到岛屿，调用dfs方法dfs(map, i, m - 1);}}// 然后检查左边界和右边界for (int j = 0; j < m; j++) {if (map[0][j] == 1) {// 如果在左边界找到岛屿，调用dfs方法dfs(map, 0, j);}if (map[n - 1][j] == 1) {// 如果在右边界找到岛屿，调用dfs方法dfs(map, n - 1, j);}}// 重置岛屿的面积计数，因为边界的岛屿可能与内部岛屿相连size = 0;// 再次遍历整个地图，寻找剩余的岛屿并进行深度优先搜索for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 如果找到未访问的岛屿，调用dfs方法if (map[i][j] == 1) {dfs(map, i, j);}}}// 输出找到的岛屿的总面积System.out.println(size);}
}水流问题
边界问题
103. 水流问题
import java.util.*;public class Main {// 定义四个方向的移动，分别对应右、下、左、上static int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 深度优先搜索（DFS）函数，用于遍历地图static void dfs(int[][] map, boolean[][] isUsed, int x, int y) {// 标记当前位置已被访问isUsed[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 < map.length &&nextY >= 0 && nextY < map[0].length &&map[x][y] <= map[nextX][nextY] &&isUsed[nextX][nextY] == false) {// 递归调用DFS函数，继续遍历下一个位置dfs(map, isUsed, nextX, nextY);}}}public static void main(String[] args) {// 创建Scanner对象，用于读取输入Scanner input = new Scanner(System.in);// 读取地图的行数和列数int n = input.nextInt();int m = input.nextInt();// 创建二维数组，用于存储地图的高度信息int[][] map = new int[n][m];// 读取地图的每一行数据for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {map[i][j] = input.nextInt();}}// 创建两个二维布尔数组，用于标记从第一组和第二组边界出发可以遍历的节点boolean[][] firstIsUsed = new boolean[n][m];boolean[][] secondIsUsed = new boolean[n][m];// 从最上和最下行的节点出发，向两侧遍历for (int i = 0; i < n; i++) {dfs(map, firstIsUsed, i, 0); // 遍历最左列dfs(map, secondIsUsed, i, m - 1); // 遍历最右列}// 从最左和最右列的节点出发，向上下遍历for (int j = 0; j < m; j++) {dfs(map, firstIsUsed, 0, j); // 遍历最上行dfs(map, secondIsUsed, n - 1, j); // 遍历最下行}// 遍历整个地图，找出同时被两组边界访问过的节点for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (firstIsUsed[i][j] && secondIsUsed[i][j]) {System.out.println(i + " " + j); // 输出这些节点的坐标}}}// 关闭输入流input.close();}
}建造最大岛屿（难）
104. 建造最大岛屿
import java.util.*;public class Main {// 用于标记不同岛屿的变量static int mark = 0;// 用于计数当前岛屿的大小static int count = 0;// 定义四个方向的移动，分别对应右、下、左、上static int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 深度优先搜索（DFS）函数，用于遍历岛屿static void dfs(int[][] map, boolean[][] isUsed, int x, int y) {// 标记当前位置已被访问isUsed[x][y] = true;// 标记当前位置属于当前岛屿map[x][y] = mark;// 增加当前岛屿的大小计数count++;// 遍历四个方向for (int i = 0; i < 4; i++) {// 计算下一个位置的坐标int nextX = x + dir[i][0];int nextY = y + dir[i][1];// 检查下一个位置是否在地图范围内，并且未被访问过，且当前位置的高度为1（陆地）if (nextX >= 0 && nextX < map.length &&nextY >= 0 && nextY < map[0].length &&isUsed[nextX][nextY] == false &&map[nextX][nextY] == 1) {// 递归调用DFS函数，继续遍历下一个位置dfs(map, isUsed, nextX, nextY);}}}public static void main(String[] args) {// 创建Scanner对象，用于读取输入Scanner input = new Scanner(System.in);// 读取地图的行数和列数int n = input.nextInt();int m = input.nextInt();// 创建二维数组，用于存储地图的信息int[][] map = new int[n][m];// 读取地图的每一行数据for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {map[i][j] = input.nextInt();}}// 标记是否所有位置都是岛屿（陆地）boolean isAllIsland = true;// 设置当前岛屿的标记为2，因为1代表陆地mark = 2;// 创建二维布尔数组，用于标记每个位置是否被访问过boolean[][] isUsed = new boolean[n][m];// 创建HashMap，用于存储每个岛屿的大小Map<Integer, Integer> getSize = new HashMap<>();// 遍历整个地图for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 如果遇到水域（0），则不是所有位置都是岛屿if (map[i][j] == 0)isAllIsland = false;// 如果遇到陆地（1），则进行DFS遍历if (map[i][j] == 1) {count = 0; // 重置岛屿大小计数dfs(map, isUsed, i, j); // 进行DFS遍历// 将当前岛屿的大小存入HashMapgetSize.put(mark, count);mark++; // 更新岛屿标记}}}// 创建HashSet，用于存储已经遍历过的岛屿标记Set<Integer> containsMark = new HashSet<>();// 用于存储最大区域的大小int ret = 0;// 如果所有位置都是岛屿，则最大区域的大小为整个地图的大小if (isAllIsland) {ret = n * m;}// 再次遍历整个地图for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 如果当前位置是水域（0）if (map[i][j] == 0) {containsMark.clear(); // 清空HashSetint localSize = 1; // 当前水域的大小至少为1// 遍历四个方向for (int k = 0; k < 4; k++) {int nextX = i + dir[k][0];int nextY = j + dir[k][1];// 检查下一个位置是否在地图范围内if (nextX >= 0 && nextX < map.length &&nextY >= 0 && nextY < map[0].length) {int curMark = map[nextX][nextY];// 如果当前位置未被遍历过，并且HashMap中存在对应的岛屿大小if (!containsMark.contains(curMark)&& getSize.containsKey(curMark)) {localSize += getSize.get(curMark); // 增加当前水域的大小containsMark.add(curMark); // 将当前岛屿标记加入HashSet}}}// 更新最大区域的大小ret = Math.max(localSize, ret);}}}// 输出最大区域的大小System.out.println(ret);}
}有向图的完全可达性
105. 有向图的完全可达性
import java.util.*;// 主类
public class Main {// 深度优先搜索（DFS）方法，用于遍历图static void dfs(List<List<Integer>> map, boolean[] isUsed, int s) {// 如果当前节点已经被访问过，则直接返回if (isUsed[s] == true) {return;}// 标记当前节点为已访问isUsed[s] = true;// 获取当前节点的所有邻接节点List<Integer> localMap = map.get(s);// 遍历所有邻接节点，并递归调用DFS方法for (int num : localMap) {dfs(map, isUsed, num);}}// 主方法，程序的入口点public static void main(String[] args) {// 创建一个Scanner对象，用于从控制台读取输入Scanner input = new Scanner(System.in);// 读取顶点的数量int n = input.nextInt();// 读取边的数量int k = input.nextInt();// 创建一个邻接表，用于表示图List<List<Integer>> map = new ArrayList<>();for (int i = 0; i < n; i++) {// 初始化每个顶点的邻接列表map.add(new ArrayList<Integer>());}// 读取所有的边，并添加到邻接表中for (int i = 0; i < k; i++) {int s = input.nextInt(); // 读取边的起始顶点int t = input.nextInt(); // 读取边的终止顶点// 将边添加到邻接表中，注意数组是从0开始的，所以需要减1map.get(s - 1).add(t - 1);}// 创建一个布尔数组，用于标记每个顶点是否被访问过boolean isUsed[] = new boolean[n];// 从顶点0开始进行深度优先搜索dfs(map, isUsed, 0);// 检查是否有未被访问的顶点，如果有，则输出-1并结束程序for (boolean bool : isUsed) {if (bool == false) {System.out.println(-1);return;}}// 如果所有顶点都被访问过，则输出1System.out.println(1);// 关闭Scanner对象input.close();}
}bfs广搜
模板-岛屿数量
99. 岛屿数量
import java.util.*; // 导入 Java 的集合框架public class Main {// 定义四个方向的移动：右、下、左、上static int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 广度优先搜索 (BFS) 方法static void bfs(int map[][], int x, int y, boolean isVisited[][]) {// 使用双端队列来实现 BFSArrayDeque<int[]> deque = new ArrayDeque<>();// 将起始点 (x, y) 加入队列deque.addFirst(new int[]{x, y});// 标记起始点为已访问isVisited[x][y] = true;// 当队列不为空时，继续进行 BFSwhile (!deque.isEmpty()) {// 从队列中取出当前点int local[] = deque.removeFirst();int curX = local[0]; // 当前点的 x 坐标int curY = local[1]; // 当前点的 y 坐标// 遍历四个方向for (int i = 0; i < 4; i++) {// 计算下一个点的坐标int nextX = curX + dir[i][0];int nextY = curY + dir[i][1];// 检查下一个点是否在地图范围内，未被访问且为 1（可通行）if (nextX >= 0 && nextX < map.length && nextY >= 0&& nextY < map[0].length && !isVisited[nextX][nextY] && map[nextX][nextY] == 1) {// 将可通行的下一个点加入队列deque.add(new int[]{nextX, nextY});// 标记下一个点为已访问isVisited[nextX][nextY] = true;}}}}public static void main(String[] args) {Scanner input = new Scanner(System.in); // 创建输入扫描器int n = input.nextInt(); // 读取地图的行数int m = input.nextInt(); // 读取地图的列数// 初始化地图，额外多一行和一列以避免边界问题int map[][] = new int[n + 1][m + 1];// 读取地图数据for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {map[i][j] = input.nextInt(); // 读取每个点的值}}// 初始化访问标记数组boolean isVisited[][] = new boolean[n + 1][m + 1];int result = 0; // 记录连通区域的数量// 遍历整个地图for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 如果当前点未被访问且为 1，说明发现了一个新的连通区域if (!isVisited[i][j] && map[i][j] == 1) {bfs(map, i, j, isVisited); // 从该点开始 BFSresult++; // 计数增加}}}// 输出连通区域的数量System.out.println(result);}
}岛屿的最大面积（广搜版）
边界问题
100. 岛屿的最大面积
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;// 主类
public class Main {// 定义一个静态变量maxSize，用于记录找到的最大连通区域的大小static int maxSize = 0;// 定义一个二维数组dir，表示四个方向（右、下、左、上）的移动static int dir[][] = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 广度优先搜索（BFS）方法，用于遍历地图上的连通区域static int bfs(int[][] map, boolean[][] isUsed, int x, int y) {// 标记当前位置为已访问isUsed[x][y] = true;// 初始化当前连通区域的大小为1（当前位置）int localSize = 1;// 创建一个双端队列deque，用于实现BFSDeque<int[]> deque = new ArrayDeque<>();// 将当前位置加入队列deque.addFirst(new int[]{x, y});// 当队列不为空时，继续进行BFSwhile(!deque.isEmpty()) {// 从队列中取出当前点int local[] = deque.removeLast();int localx = local[0]; // 当前点的x坐标int localy = local[1]; // 当前点的y坐标// 遍历四个方向for(int i = 0 ; i < 4 ; i++ ) {// 计算下一个点的坐标int nextX = localx + dir[i][0];int nextY = localy + dir[i][1];// 检查下一个点是否在地图范围内，未被访问且为1（可通行）if(nextX >= 0 && nextX < map.length &&nextY >= 0 && nextY < map[0].length &&isUsed[nextX][nextY] == false &&map[nextX][nextY] == 1) {// 将可通行的下一个点加入队列isUsed[nextX][nextY] = true;deque.addLast(new int[]{nextX, nextY});// 更新当前连通区域的大小localSize++;}}}// 返回当前连通区域的大小return localSize;}// 主方法public static void main (String[] args) {// 创建一个Scanner对象，用于读取用户输入Scanner input = new Scanner(System.in);// 读取地图的行数和列数int n = input.nextInt();int m = input.nextInt();// 创建一个二维数组map，用于存储地图信息，1表示可以访问，0表示不可以访问int[][] map = new int[n][m];// 读取地图的具体信息for(int i = 0 ; i < n; i++) {for(int j = 0 ; j < m; j++) {map[i][j] = input.nextInt();}}// 创建一个二维数组isUsed，用于标记地图上的位置是否已经被访问过boolean[][] isUsed = new boolean[n][m];// 遍历地图，找出所有未访问的1（可以访问的位置），并使用BFS方法遍历连通区域for(int i = 0 ; i < n; i++) {for(int j = 0 ; j < m; j++) {// 如果当前位置没有被访问过，并且该位置为1if(isUsed[i][j] == false && map[i][j] == 1) {// 调用BFS方法，从当前位置开始遍历连通区域int localSize = bfs(map, isUsed, i, j);// 更新最大连通区域的大小maxSize = Math.max(localSize, maxSize);}}}// 输出最大连通区域的大小System.out.println(maxSize);}
}字符串接龙（无向图！）
110. 字符串接龙
import java.util.*;public class Main {// 使用广度优先搜索（BFS）算法计算从一个字符串到另一个字符串的最少步数static int bfs(String str[], Set<String> strList) {// 初始化起始字符串和结束字符串String beginStr = str[0];String endStr = str[1];// 使用双端队列来存储待处理的字符串Deque<String> deque = new ArrayDeque<>();// 将起始字符串加入队列deque.add(beginStr);// 使用HashMap来存储每个字符串到起始字符串的步数Map<String, Integer> path = new HashMap<>();// 设置起始字符串的步数为0path.put(beginStr, 1);// 开始广度优先搜索while (!deque.isEmpty()) {// 从队列中取出一个字符串String curStr = deque.removeLast();// 获取当前字符串到起始字符串的步数int count = path.get(curStr);// 遍历当前字符串的每个字符for (int i = 0; i < curStr.length(); i++) {// 将当前字符串转换为字符数组char[] curStrArray = curStr.toCharArray();// 遍历所有小写字母for (char ch = 'a'; ch <= 'z'; ch++) {// 替换当前位置的字符curStrArray[i] = ch;// 将字符数组转换回字符串String newStr = String.valueOf(curStrArray);// 如果新字符串等于结束字符串，返回步数if (newStr.equals(endStr)) {return count + 1;}// 如果新字符串在字符串列表中，并且没有被处理过if (strList.contains(newStr) && !path.containsKey(newStr)) {// 将新字符串加入队列deque.addFirst(newStr);// 记录新字符串到起始字符串的步数path.put(newStr, count + 1);}}}}// 如果没有找到结束字符串，返回0return 0;}public static void main(String[] args) {// 创建Scanner对象，用于读取输入Scanner input = new Scanner(System.in);// 读取字符串的数量int n = input.nextInt();// 读取下一行，忽略换行符input.nextLine();// 读取起始和结束字符串String BEStr = input.nextLine();// 将起始和结束字符串分割并存储在数组中String[] str = BEStr.split(" ");// 创建HashSet，用于存储字符串列表Set<String> strList = new HashSet<>();// 读取n个字符串并加入HashSetfor (int i = 0; i < n; i++) {strList.add(input.nextLine());}// 调用bfs函数，计算步数int ret = bfs(str, strList);// 输出结果System.out.println(ret);}
}非深搜广搜的其他类型题目
岛屿的周长
106. 岛屿的周长
import java.util.*;public class Main {public static void main(String[] args) {// 创建一个 Scanner 对象来读取用户的输入Scanner input = new Scanner(System.in);// 读取用户输入的行数和列数int n = input.nextInt();int m = input.nextInt();// 创建一个二维数组来存储地图信息，初始值都为0int map[][] = new int[n][m];// 读取地图信息，填充到二维数组中for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {map[i][j] = input.nextInt();}}// 关闭 Scanner 对象，释放资源input.close();// 定义四个方向的移动，分别是右、下、左、上int dir[][] = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 初始化返回值，用于计数int ret = 0;// 遍历地图的每个格子for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 如果当前格子的值为1，表示是一个陆地格子if (map[i][j] == 1) {// 遍历四个方向for (int k = 0; k < 4; k++) {// 计算下一个格子的坐标int nextX = i + dir[k][0];int nextY = j + dir[k][1];// 检查下一个格子是否在地图范围内，并且不是陆地（值为0）// 注意：这里使用 map.length 和 map[0].length 来获取行数和列数if (nextX < 0 || nextX >= map.length ||nextY < 0 || nextY >= map[0].length ||map[nextX][nextY] == 0) {ret++;}}}}}// 输出结果，即周围不是陆地的格子数System.out.println(ret);}
}并查集
理论在其他文章
寻找存在的路径
无向图的路径问题
107. 寻找存在的路径
import java.util.*;public class Main {// 定义并查集的大小static int n = 101;// 用于存储每个元素的父节点，初始时每个元素的父节点都是自己static int father[] = new int[n];// 初始化并查集static void init() {for (int i = 0; i < n; i++) {father[i] = i; // 每个元素的父节点设置为自己}}// 查找元素u的根节点static int find(int u) {return u == father[u] ? u : find(father[u]); // 如果u的父节点是它自己，说明u就是根节点}// 合并元素u和v所在的集合static void join(int u, int v) {u = find(u); // 找到u的根节点v = find(v); // 找到v的根节点if (u == v) {return; // 如果u和v已经在同一个集合中，不需要合并}father[v] = u; // 将v的根节点设置为u，这样v所在的集合就被合并到了u所在的集合中}// 判断元素u和v是否在同一个集合中static boolean isSame(int u, int v) {u = find(u); // 找到u的根节点v = find(v); // 找到v的根节点return u == v; // 如果根节点相同，则u和v在同一个集合中}public static void main(String[] args) {// 初始化并查集init();// 创建Scanner对象用于读取输入Scanner input = new Scanner(System.in);// 读取测试用例的数量int n = input.nextInt();// 读取操作的数量int m = input.nextInt();// 处理每个操作for (int i = 0; i < m; i++) {int u = input.nextInt(); // 读取操作中的第一个元素int v = input.nextInt(); // 读取操作中的第二个元素join(u, v); // 合并u和v所在的集合}// 读取源点和目标点int source = input.nextInt();int destination = input.nextInt();// 判断源点和目标点是否在同一个集合中if (isSame(source, destination)) {System.out.println(1); // 如果在同一个集合中，输出1} else {System.out.println(0); // 如果不在同一个集合中，输出0}// 关闭Scanner对象input.close();}
}冗余连接（无向图）
108. 冗余连接
import java.util.*;public class Main {// 定义并查集的最大元素数量static int N = 1001;// 用于存储每个元素的父节点，初始时每个元素的父节点都是自己static int father[] = new int[N];// 初始化并查集static void init() {for (int i = 0; i < N; i++) {father[i] = i; // 每个元素的父节点设置为自己}}// 查找元素u的根节点static int find(int u) {return u == father[u] ? u : find(father[u]); // 如果u的父节点是它自己，说明u就是根节点}// 合并元素u和v所在的集合static void join(int u, int v) {u = find(u); // 找到u的根节点v = find(v); // 找到v的根节点if (u == v) {return; // 如果u和v已经在同一个集合中，不需要合并}father[v] = u; // 将v的根节点设置为u，这样v所在的集合就被合并到了u所在的集合中}// 判断元素u和v是否在同一个集合中static boolean isSame(int u, int v) {u = find(u); // 找到u的根节点v = find(v); // 找到v的根节点return u == v; // 如果根节点相同，则u和v在同一个集合中}public static void main(String[] args) {// 初始化并查集init();// 创建Scanner对象用于读取输入Scanner input = new Scanner(System.in);// 读取操作的数量int n = input.nextInt();// 处理每个操作for (int i = 0; i < n; i++) {int s = input.nextInt(); // 读取操作中的第一个元素int t = input.nextInt(); // 读取操作中的第二个元素// 判断s和t是否已经在同一个集合中if (isSame(s, t)) {System.out.println(s + " " + t); // 如果已经在同一个集合中，输出这对元素并结束程序return;} else {join(s, t); // 如果不在同一个集合中，将它们所在的集合合并}}// 关闭Scanner对象input.close();}
}冗余连接II（有向图）
109. 冗余连接II
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {// 用于存储每个节点的父节点，初始化时每个节点的父节点都是自己static int father[] = new int[1001];// 初始化每个节点的父节点static void init() {for (int i = 0; i < 1001; i++) {father[i] = i;}}// 查找节点u的根节点，使用路径压缩static int find(int u) {return u == father[u] ? u : find(father[u]);}// 判断两个节点是否在同一个集合中（是否有相同的根节点）static boolean isSame(int u, int v) {u = find(u);v = find(v);return u == v;}// 将节点u和v合并到同一个集合中static void join(int u, int v) {u = find(u);v = find(v);if (u == v)return;father[v] = u;}// 检测移除指定边后是否能够形成一棵树static boolean isTreeAfterRemoveEdge(int deleteEdge, int map[][]) {init();// 遍历所有边，跳过要删除的边for (int i = 1; i < map.length; i++) {if (deleteEdge == i)continue;// 如果两个节点已经在同一个集合中，则不能形成树if (isSame(map[i][0], map[i][1])) {return false;} else {// 将两个节点合并到同一个集合中join(map[i][0], map[i][1]);}}// 如果所有边都能合并，则可以形成树return true;}// 检测图中是否存在环static void isCircle(int map[][]) {init();// 遍历所有边，如果发现两个节点已经在同一个集合中，则输出这条边并返回for (int i = 1; i < map.length; i++) {if (isSame(map[i][0], map[i][1])) {System.out.println(map[i][0] + " " + map[i][1]);return;} else {join(map[i][0], map[i][1]);}}}public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt(); // 读取边的数量// 存储每个节点的度数int degree[] = new int[n + 1];// 存储边的信息，map[i][0]和map[i][1]分别表示第i条边的两个节点int map[][] = new int[n + 1][2];// 读取边的信息for (int i = 1; i <= n; i++) {int u = input.nextInt();int v = input.nextInt();map[i][0] = u;map[i][1] = v;degree[v]++;}// 存储度数为2的边的索引List<Integer> twoDegree = new ArrayList<>();for (int i = 1; i <= n; i++) {if (degree[map[i][1]] == 2) {twoDegree.add(i);}}// 如果存在度数为2的节点if (!twoDegree.isEmpty()) {int firstEdge = twoDegree.get(twoDegree.size() - 1);// 尝试移除最后一条度数为2的边，检测是否能够形成树if (isTreeAfterRemoveEdge(firstEdge, map)) {System.out.println(map[firstEdge][0] + " " + map[firstEdge][1]);} else {// 如果不能形成树，则尝试移除倒数第二条度数为2的边System.out.println(map[twoDegree.get(twoDegree.size() - 2)][0] + " "+ map[twoDegree.get(twoDegree.size() - 2)][1]);}} else {// 如果不存在度数为2的节点，则检测图中是否存在环isCircle(map);}}
}构建最小生成树
prim算法
数据结构-prim算法-CSDN博客
拓扑排序
数据结构-拓扑排序笔记-CSDN博客