第十一章：图论part04
110. 字符串接龙
经过上面的练习，大家可能会感觉 广搜不过如此，都刷出自信了，本题让大家初步感受一下，广搜难不在广搜本身，而是如何应用广搜。
文章讲解
思路
image.png
实际上就是求最短路径的长度
需要解决两个问题
- 图中的点如何连在一起的
- 判断点与点之间是否有连线，需要判断是不是差一个字符，如果差一个字符，那就是有链接。
- 起点和终点的最短路径长度
- 这里无向图求最短路，广搜最为合适，广搜只要搜到了终点，那么一定是最短的路径。因为广搜就是以起点中心向四周扩散的搜索。
- 本题如果用深搜，会比较麻烦，要在到达终点的不同路径中选则一条最短路。 而广搜只要达到终点，一定是最短路。
注意
- 本题是一个无向图，需要用标记位，标记着节点是否走过，否则就会死循环！
- 使用set来检查字符串是否出现在字符串集合里更快一些
我这样写过不了不知道为什么
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 输入单词列表的大小
sc.nextLine(); // 清除缓冲区
String[] strs = sc.nextLine().split(" "); // 输入起始单词和结束单词
List<String> wordList = new ArrayList<>();
for (int i = 0; i < n; i++) {
wordList.add(sc.next()); // 添加每一个单词到列表中
}
int result = ladderLength(strs[0], strs[1], wordList);
System.out.println(result); // 输出结果
}
public static int ladderLength(String beginStr, String endStr, List<String> strList) {
// 将单词列表转换为一个Set以便快速查找
Set<String> wordSet = new HashSet<>(strList);
// 如果endStr不在字典中，直接返回0，因为无法转换
if (!wordSet.contains(endStr)) {
return 0;
}
// 用于记录每个单词是否访问过，以及它在转换路径中的长度
Map<String, Integer> pathMap = new HashMap<>();
// 初始化队列，用于BFS遍历
Queue<String> queue = new LinkedList<>();
queue.offer(beginStr); // 将起始单词加入队列
pathMap.put(beginStr, 1); // 设置起始单词的路径长度为1
// 开始BFS遍历
while (!queue.isEmpty()) {
// 从队列中取出一个单词
String currentWord = queue.poll();
int currentPath = pathMap.get(currentWord); // 当前路径长度
// 对单词的每一个字符进行替换尝试
for (int i = 0; i < currentWord.length(); i++) {
char[] wordArray = currentWord.toCharArray(); // 将字符串转换为字符数组
// 尝试将每个字符替换为'a'到'z'中的任意一个字母
for (char c = 'a'; c <= 'z'; c++) {
wordArray[i] = c; // 替换字符
String newWord = new String(wordArray); // 生成新单词
// 如果新单词就是目标单词，返回路径长度
if (newWord.equals(endStr)) {
return currentPath + 1;
}
// 如果新单词在字典中，且之前未被访问过
if (wordSet.contains(newWord) && !pathMap.containsKey(newWord)) {
pathMap.put(newWord, currentPath + 1); // 记录新单词的路径长度
queue.offer(newWord); // 将新单词加入队列
}
}
}
}
// 如果没有找到目标单词，返回0
return 0;
}
}
这个能过
import java.util.*;
public class Main {
// 全局变量用于存储单词集合和路径信息
static Set<String> wordSet = new HashSet<>();
static Map<String, Integer> pathMap = new HashMap<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 输入单词列表的大小
String beginStr = sc.next(); // 起始单词
String endStr = sc.next(); // 目标单词
sc.nextLine(); // 清除缓冲区
// 将所有单词添加到wordSet中
for (int i = 0; i < n; i++) {
wordSet.add(sc.next());
}
// 初始节点的路径长度设置为1
pathMap.put(beginStr, 1);
// 使用队列进行广度优先搜索
Queue<String> queue = new LinkedList<>();
queue.offer(beginStr); // 将起始单词加入队列
// 开始BFS遍历
while (!queue.isEmpty()) {
String currentWord = queue.poll(); // 取出当前单词
int currentPath = pathMap.get(currentWord); // 当前路径长度
// 对单词的每一个字符进行替换尝试
for (int i = 0; i < currentWord.length(); i++) {
char[] wordArray = currentWord.toCharArray(); // 将字符串转换为字符数组
// 尝试将每个字符替换为'a'到'z'中的任意一个字母
for (char c = 'a'; c <= 'z'; c++) {
wordArray[i] = c; // 替换字符
String newWord = new String(wordArray); // 生成新单词
// 如果新单词就是目标单词，返回路径长度
if (newWord.equals(endStr)) {
System.out.println(currentPath + 1);
return;
}
// 如果新单词在字典中，且之前未被访问过
if (wordSet.contains(newWord) && !pathMap.containsKey(newWord)) {
pathMap.put(newWord, currentPath + 1); // 记录新单词的路径长度
queue.offer(newWord); // 将新单词加入队列
}
}
}
}
// 如果没有找到目标单词，返回0
System.out.println(0);
}
}
之后要放到编译器里调试一下
105. 有向图的完全可达性
深搜有细节，同样是深搜两种写法的区别，以及什么时候需要回溯操作呢？
文章讲解
思路
本题是一个有向图搜索全路径的问题。 只能用深搜（DFS）或者广搜（BFS）来搜。
深搜三部曲
1. 确认递归函数，参数
- 需要传入地图，需要知道当前我们拿到的key，以至于去下一个房间。
- 同时还需要一个数组，用来记录我们都走过了哪些房间，这样好知道最后有没有把所有房间都遍历的，可以定义一个一维数组。
所以 递归函数参数如下：
// key 当前得到的key
// visited 记录访问过的房间
void dfs(List<List<Integer>> graph, int key, boolean[] visited) {
// 具体逻辑在下面实现
}
2. 确认终止条件
- 遍历的时候什么时候中止，要想清楚递归的时候是处理当前访问的节点，还是处理下一个要访问的节点。
- 首先明确，本题中“处理” = 用 visited数组来记录访问过的节点，该节点默认 数组里元素都是false，把元素标记为true就是处理 本节点了。
- 如果我们是处理当前访问的节点，当前访问的节点如果是 true ，说明是访问过的节点，那就终止本层递归，如果不是true，我们就把它赋值为true，因为这是我们处理本层递归的节点。
if (visited[key]) {
return;
}
visited[key] = true;
List<Integer> keys = graph.get(key);
for (int nextKey : keys) {
// 深度优先搜索遍历
dfs(graph, nextKey, visited);
}
写法二：处理下一个要访问的节点
void dfs(List<List<Integer>> graph, int key, boolean[] visited) {
List<Integer> keys = graph.get(key);
for (int nextKey : keys) {
if (!visited[nextKey]) { // 确认下一个是没访问过的节点
visited[nextKey] = true;
dfs(graph, nextKey, visited);
}
}
}
3. 处理目前搜索节点出发的路径
- 上面终止条件有两种不同的写法，所以递归也有两种写法
- 为什么本题就没有回溯呢？只有在需要搜索一条可行路径的时候，就需要回溯操作了，因为没有回溯，就没法“调头”。本题只是求节点1能否到所有节点，就不必回溯，只要遍历过的节点都一律标记上。
写法一：DFS 处理当前访问的节点
import java.util.*;
public class Main{
// 写法一：DFS 处理当前访问的节点
public static void dfs(List<List<Integer>> graph, int key, boolean[] visited){
if(visited[key]) return;
visited[key] = true;
List<Integer> keys = graph.get(key);
for(int nextKey : keys){
dfs(graph, nextKey, visited);
}
}
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
List<List<Integer>> graph = new ArrayList<>(N + 1);
for(int i = 0; i <= N; i++){
graph.add(new ArrayList<>());
}
for(int i = 0; i < K; i++){
int s = sc.nextInt();
int t = sc.nextInt();
graph.get(s).add(t);
}
boolean[] visited = new boolean[N + 1];
dfs(graph, 1, visited);
// 检查是否都访问到了 节点编号从1开始
for(int i = 1; i <= N; i++){
if(!visited[i]){
System.out.println(-1);
return;
}
}
System.out.println(1);
}
}
写法二：DFS 处理下一个要访问的节点
import java.util.*;
public class Main {
// DFS方法：处理下一个要访问的节点
public static void dfs(List<List<Integer>> graph, int key, boolean[] visited) {
List<Integer> keys = graph.get(key);
for (int nextKey : keys) {
if (!visited[nextKey]) { // 确认下一个是没访问过的节点
visited[nextKey] = true;
dfs(graph, nextKey, visited);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 节点数
int m = sc.nextInt(); // 边数
List<List<Integer>> graph = new ArrayList<>(n + 1);
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
int s = sc.nextInt();
int t = sc.nextInt();
graph.get(s).add(t);
}
boolean[] visited = new boolean[n + 1];
visited[1] = true; // 节点1 预先处理
dfs(graph, 1, visited);
// 检查是否都访问到了
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
System.out.println(-1);
return;
}
}
System.out.println(1);
}
}
106. 岛屿的周长
简单题，避免大家惯性思维，建议大家先独立做题。
文章讲解
思路
解法一
遍历每一个空格，遇到岛屿（即值为 1）时，计算其上下左右四个方向的情况。如果在这些方向上有水域（即值为 0），或者超出了网格的边界，则认为这是岛屿的一条边，并增加边的计数。
image.png
import java.util.Scanner;
public class Main {
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();
}
}
int[][] direction = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int result = 0;
// 遍历每一个空格
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1) { // 找到岛屿
for (int k = 0; k < 4; k++) { // 计算四个方向
int x = i + direction[k][0];
int y = j + direction[k][1];
// 判断边界和水域
if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) {
result++;
}
}
}
}
}
System.out.println(result);
}
}
解法二
首先，计算出总的岛屿数量，然后假设每个岛屿的初始边数是 4，即总边数为 岛屿数量 * 4。然后，计算相邻岛屿的数量，因为每对相邻的岛屿共用一条边，因此每对相邻的岛屿会减少 2 条边。
image.png
import java.util.Scanner;
public class Main {
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();
}
}
int sum = 0; // 陆地数量
int cover = 0; // 相邻数量
// 遍历每一个空格
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == 1){
sum++;
// 统计上边相邻陆地
if(i - 1 >= 0 && grid[i - 1][j] == 1) cover++;
// 统计下边相邻陆地
if(j - 1 >= 0 && grid[i][j - 1] == 1) cover++;
}
}
}
int result = sum * 4 - cover * 2;
System.out.println(result);
}
}
