代码随想录算法训练营第四十六天 | 图论 Part04

571 字

3 分钟

代码随想录算法训练营第四十六天 | 图论 Part04

2025-08-02

算法

图论基础、字符串接龙、岛屿周长问题

/

LeetCode

/

Python

卡码网：110. 字符串接龙#

题目链接

思路：

将所有中间词放入集合 word_set，若 endStr 不在其中且不等于 beginStr，则加入集合。
用 BFS（队列 queue）从 beginStr 开始，每一步扩展所有与当前字符串仅差一个字符的词，并将其从集合中移除以避免重复访问。
当遇到 endStr 时输出当前变换长度，否则结束后输出 0。

1
import sys
2
from collections import deque
3

4
def main():
5
    data = sys.stdin.read().split()
6
    N = int(data[0])
7
    beginStr, endStr = data[1], data[2]
8
    strList = data[3:3+N]
9

10
    word_set = set(strList)
11
    if endStr != beginStr and endStr not in word_set:
12
        word_set.add(endStr)  # 加入终点，方便BFS找到
13

14
    queue = deque()
15
    queue.append((beginStr, 1))
16

17
    def is_one_char_diff(s1, s2):
18
        if len(s1) != len(s2):
19
            return False
20
        return sum(c1 != c2 for c1, c2 in zip(s1, s2)) == 1
21

22
    while queue:
23
        current, length = queue.popleft()
24
        if current == endStr:
25
            print(length)
26
            return
27

28
        to_remove = []
29
        for word in word_set:
30
            if is_one_char_diff(current, word):
31
                queue.append((word, length + 1))
32
                to_remove.append(word)
33
        for w in to_remove:
34
            word_set.remove(w)
35

36
    print(0)
37

38
if __name__ == "__main__":
39
    main()

卡码网：105. 有向图的完全联通#

题目链接

思路：

构建邻接表 graph，从节点 1 开始 BFS，使用 visited 数组标记已访问节点。
遍历完所有可达节点后，若访问计数等于 N，则输出 1，否则输出 -1。

1
import sys
2
from collections import deque
3

4
def main():
5
    data = sys.stdin.read().strip().split()
6
    N, K = int(data[0]), int(data[1])
7
    edges = data[2:]
8

9
    graph = [[] for _ in range(N+1)]
10
    for i in range(0, 2*K, 2):
11
        s, t = int(edges[i]), int(edges[i+1])
12
        graph[s].append(t)
13

14
    visited = [False] * (N+1)
15
    queue = deque([1])
16
    visited[1] = True
17
    count = 1
18

19
    while queue:
20
        node = queue.popleft()
21
        for nxt in graph[node]:
22
            if not visited[nxt]:
23
                visited[nxt] = True
24
                count += 1
25
                queue.append(nxt)
26

27
    print(1 if count == N else -1)
28

29
if __name__ == "__main__":
30
    main()

卡码网：106. 岛屿周长#

题目链接

思路：

遍历整个网格，对每个值为 1 的格子，检查其上、下、左、右四个方向：
若相邻格子为水（0）或越界，则该边贡献周长 1。
累加所有陆地格子的周长，最后输出总和。

1
import sys
2
input = sys.stdin.read
3

4
def main():
5
    data = input().split()
6
    n, m = int(data[0]), int(data[1])
7
    index = 2
8
    grid = [[0] * m for _ in range(n)]
9
    for i in range(n):
10
        for j in range(m):
11
            grid[i][j] = int(data[index])
12
            index += 1
13

14
    res = 0
15
    for i in range(n):
16
        for j in range(m):
17
            if grid[i][j] == 1:
18
                # 上
19
                if i == 0 or grid[i - 1][j] == 0:
20
                    res += 1
21
                # 下
22
                if i == n - 1 or grid[i + 1][j] == 0:
23
                    res += 1
24
                # 左
25
                if j == 0 or grid[i][j - 1] == 0:
26
                    res += 1
27
                # 右
28
                if j == m - 1 or grid[i][j + 1] == 0:
29
                    res += 1
30
    print(res)
31

32
if __name__ == "__main__":
33
    main()