参考文献 代码随想录
一、字符串接龙
题目描述
字典 strList 中从字符串 beginStr 和 endStr 的转换序列是一个按下述规格形成的序列：
1. 序列中第一个字符串是 beginStr。
2. 序列中最后一个字符串是 endStr。
3. 每次转换只能改变一个字符。
4. 转换过程中的中间字符串必须是字典 strList 中的字符串，且strList里的每个字符串只用使用一次。
给你两个字符串 beginStr 和 endStr 和一个字典 strList，找到从 beginStr 到 endStr 的最短转换序列中的字符串数目。如果不存在这样的转换序列，返回 0。
输入描述
第一行包含一个整数 N，表示字典 strList 中的字符串数量。 第二行包含两个字符串，用空格隔开，分别代表 beginStr 和 endStr。 后续 N 行，每行一个字符串，代表 strList 中的字符串。
输出描述
输出一个整数，代表从 beginStr 转换到 endStr 需要的最短转换序列中的字符串数量。如果不存在这样的转换序列，则输出 0。
输入示例
6
abc def
efc
dbc
ebc
dec
dfc
yhn输出示例
4提示信息
从 startStr 到 endStr，在 strList 中最短的路径为 abc -> dbc -> dec -> def，所以输出结果为 4，如图：
数据范围：
2 <= N <= 500
思路
以示例1为例，从这个图中可以看出 abc 到 def的路线 不止一条，但最短的一条路径上是4个节点。
本题只需要求出最短路径的长度就可以了，不用找出具体路径。
所以这道题要解决两个问题：
- 图中的线是如何连在一起的
- 起点和终点的最短路径长度
首先题目中并没有给出点与点之间的连线，而是要我们自己去连，条件是字符只能差一个。
所以判断点与点之间的关系，需要判断是不是差一个字符，如果差一个字符，那就是有链接。
然后就是求起点和终点的最短路径长度，这里无向图求最短路，广搜最为合适，广搜只要搜到了终点，那么一定是最短的路径。因为广搜就是以起点中心向四周扩散的搜索。
本题如果用深搜，会比较麻烦，要在到达终点的不同路径中选则一条最短路。 而广搜只要达到终点，一定是最短路。
另外需要有一个注意点：
- 本题是一个无向图，需要用标记位，标记着节点是否走过，否则就会死循环！
- 使用set来检查字符串是否出现在字符串集合里更快一些
# 广搜相对于深搜，总能率先找到目标点
# 深搜适合穷举所有可行路径
from collections import deque, defaultdict
def bfs(d_len, beginStr, endStr, strDic):
res = 0
dq = deque()
dq.append((beginStr, 1))
# 开始广搜
while dq:
tmp = dq.popleft()
for i in range(len(tmp[0])):
for j in range(26):
ttmp = list(tmp[0])
ttmp[i] = chr(j + ord("a")) # 先换成对应的数字相加，然后在化为对应的子母
ttmp = "".join(ttmp)
if ttmp == endStr: # 如果当前字符串等于最终的目标字符串，那么结束循环
return tmp[1] + 1 # 为什么要加一，因为还有算到最后字符串的长度
# print(ttmp,endStr)
if ttmp in strDic and strDic[ttmp] == 1: # 构造出的字符串必须是原数组中的元素，而且没有被访问过
strDic[ttmp] = 2
dq.append((ttmp, tmp[1] + 1))
# print(dq)
return 0
def main():
d_len = int(input())
beginStr, endStr = input().split()
strDic = defaultdict() # 使用的是临街表的形式，例如["ab":[3,5]]，动态的
for _ in range(d_len): #
strDic[input()] = 1
res = bfs(d_len, beginStr, endStr, strDic)
print(res)
if __name__ == "__main__":
main()二、105. 有向图的完全可达性
题目描述
给定一个有向图，包含 N 个节点，节点编号分别为 1，2，...，N。现从 1 号节点开始，如果可以从 1 号节点的边可以到达任何节点，则输出 1，否则输出 -1。
输入描述
第一行包含两个正整数，表示节点数量 N 和边的数量 K。 后续 K 行，每行两个正整数 s 和 t，表示从 s 节点有一条边单向连接到 t 节点。
输出描述
如果可以从 1 号节点的边可以到达任何节点，则输出 1，否则输出 -1。
输入示例
4 4
1 2
2 1
1 3
2 4输出示例
1提示信息
从 1 号节点可以到达任意节点，输出 1。
n, k = map(int, input().split())
grid = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(k):
x, y = map(int, input().split())
grid[x][y] = 1
visited = [False] * (n + 1)
def dfs(start, n):
from collections import deque
q = deque()
q.append(start)
while q:
tmp = q.pop()
for i in range(n + 1):
if grid[tmp][i] == 1 and not visited[i]:
visited[i] = True
q.append(i)
visited[1] = True # 为什么要初始化因为后面的有可能访问不到
dfs(1, n)
if visited.count(True) == n:
print(1)
else:
print(-1)数据范围：
1 <= N <= 100；
1 <= K <= 2000。
三、106. 岛屿的周长
题目描述
给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿是被水包围，并且通过水平方向或垂直方向上相邻的陆地连接而成的。
你可以假设矩阵外均被水包围。在矩阵中恰好拥有一个岛屿，假设组成岛屿的陆地边长都为 1，请计算岛屿的周长。岛屿内部没有水域。
输入描述
第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。
输出描述
输出一个整数，表示岛屿的周长。
输入示例
5 5
0 0 0 0 0
0 1 0 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0输出示例
14提示信息
岛屿的周长为 14。
数据范围：
1 <= M, N <= 50。
思路
岛屿问题最容易让人想到BFS或者DFS，但本题确实还用不上。
为了避免大家惯性思维，所以给大家安排了这道题目。
#解法一：
遍历每一个空格，遇到岛屿则计算其上下左右的空格情况。
如果该陆地上下左右的空格是有水域，则说明是一条边，如图：
陆地的右边空格是水域，则说明找到一条边。
如果该陆地上下左右的空格出界了，则说明是一条边，如图：
该陆地的下边空格出界了，则说明找到一条边。
C++代码如下：（详细注释）
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
int direction[4][2] = {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]; // 计算周边坐标x,y
if (x < 0 // x在边界上
|| x >= grid.size() // x在边界上
|| y < 0 // y在边界上
|| y >= grid[0].size() // y在边界上
|| grid[x][y] == 0) { // x,y位置是水域
result++;
}
}
}
}
}
cout << result << endl;
}
#解法二：
计算出总的岛屿数量，总的变数为：岛屿数量 * 4
因为有一对相邻两个陆地，边的总数就要减2，如图红线部分，有两个陆地相邻，总边数就要减2
那么只需要在计算出相邻岛屿的数量就可以了，相邻岛屿数量为cover。
结果 result = 岛屿数量 * 4 - cover * 2;
C++代码如下：（详细注释）
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
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++;
// 为什么没统计下边和右边？ 因为避免重复计算
}
}
}
cout << sum * 4 - cover * 2 << endl;
}n, m = map(int, input().split())
grid = []
for i in range(n):
tmp = list(map(int, input().split()))
grid.append(tmp)
visited = [[False] * (m) for _ in range(n)]
directions = [[1, 0],[-1, 0], [0, 1],[0, -1]]
res = 0
for i in range(n ):
for j in range(m):
if grid[i][j] == 1:
for direction in directions: #// 上下左右四个方向
x = i + direction[0];
y = j + direction[1]; #// 计算周边坐标x,y
if (x < 0 # // x在边界上
or x >= len(grid) #// x在边界上
or y < 0 #// y在边界上
or y >= len(grid[0]) # // y在边界上
or grid[x][y] == 0): #// x,y位置是水域
res += 1
print(res)
