深度优先搜索与回溯

import sys
sys.setrecursionlimit(10**6)

grid = [line.strip() for line in sys.stdin.read().split("\n") if line.strip()]   # 每行一串数字字符
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]

def dfs(r, c):                             # 返回 (r, c) 所在矿堆的价值；标记不回退
    if r < 0 or r >= rows or c < 0 or c >= cols:   # 越界最先判
        return 0
    if grid[r][c] == "0" or seen[r][c]:    # 空地 / 已访问
        return 0
    seen[r][c] = True
    total = int(grid[r][c])                # 银 1、金 2
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        total += dfs(r + dr, c + dc)
    return total

best = 0
for r in range(rows):
    for c in range(cols):
        if grid[r][c] != "0" and not seen[r][c]:   # 只从未访问的矿格开始一次新搜索
            best = max(best, dfs(r, c))
print(best)

自测建议：题面示例（输出 8）、全空地（输出 0）、第 10 节练习 2 的 121 / 212（输出 9）。输入按题目页参考题解读到空行或文件尾。

import sys

data = sys.stdin.read().split()
m, e = int(data[0]), int(data[1])          # 节点 1..m，e 条边
adj = [[] for _ in range(m + 1)]
for i in range(e):
    a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i])
    adj[a].append(b)
    adj[b].append(a)

color = [0] * (m + 1)                      # 0 黑、1 红；黑黑可以相邻，红红不能
count = 0

def paint(u):                              # 决定节点 u 的颜色
    global count
    if u == m + 1:                         # 所有节点都染完 → 一种方案
        count += 1
        return
    paint(u + 1)                           # 选择 1：染黑，不需要检查
    if all(color[v] == 0 for v in adj[u]): # 选择 2：染红——已染色的邻居里不能有红
        color[u] = 1
        paint(u + 1)
        color[u] = 0                       # 撤销，换下一种选择

paint(1)
print(count)

自测建议：链 1—2—3 → 5、三角形 → 4、无边 3 点 → 8、四点环 → 7。

import sys
sys.setrecursionlimit(10**6)

data = sys.stdin.read().split()
m, n = int(data[0]), int(data[1])
cells = data[2:2 + m * n]
grid = [cells[i * n:(i + 1) * n] for i in range(m)]
seen = [[False] * n for _ in range(m)]

def on_border(r, c):
    return r == 0 or r == m - 1 or c == 0 or c == n - 1

def dfs(r, c):                             # 返回 (面积, 边界格数)
    seen[r][c] = True
    area, doors = 1, (1 if on_border(r, c) else 0)
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == "O" and not seen[nr][nc]:
            a, d = dfs(nr, nc)
            area += a
            doors += d
    return area, doors

found = {}                                 # 面积 → 入口坐标列表（只记单入口区域）
for r in range(m):
    for c in range(n):
        if on_border(r, c) and grid[r][c] == "O" and not seen[r][c]:   # 只从边界上的 O 出发
            area, doors = dfs(r, c)
            if doors == 1:                 # 整块只有这一个边界格
                found.setdefault(area, []).append((r, c))

if not found:
    print("NULL")
else:
    biggest = max(found)
    if len(found[biggest]) == 1:
        r, c = found[biggest][0]
        print(r, c, biggest)
    else:
        print(biggest)                     # 多个同样大的单入口区域：只输出面积

自测建议：第 06 节的三种输出形式（3 2 5、1、NULL）与第 10 节练习 5。

import sys

data = sys.stdin.read().split()
n = int(data[0])
vals = [int(x) for x in data[1:1 + n * n]]
dist = [vals[i * n:(i + 1) * n] for i in range(n)]   # dist[x][y] 不一定等于 dist[y][x]

visited = [False] * n
visited[0] = True
best = float("inf")

def dfs(cur, count, total):                # 当前在 cur，已访问 count 个基站，路程 total
    global best
    if total >= best:                      # 已经不比当前最优短，再走也没用
        return
    if count == n:                         # 全部访问过 → 回到 0
        best = min(best, total + dist[cur][0])
        return
    for nxt in range(1, n):
        if not visited[nxt]:
            visited[nxt] = True            # 选择
            dfs(nxt, count + 1, total + dist[cur][nxt])   # 递归
            visited[nxt] = False           # 撤销

dfs(0, 1, 0)
print(best)

自测建议：第 07 节两组手算（13、3）。

def count_red_black(m, edges):
    adj = [[] for _ in range(m + 1)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    color = [0] * (m + 1)                 # 0 黑、1 红
    count = 0

    def paint(u):
        nonlocal count
        if u == m + 1:                    # 全部决定完 → 一种方案
            count += 1
            return
        paint(u + 1)                      # 选择 1：染黑，无需检查
        if all(color[v] == 0 for v in adj[u]):   # 选择 2：染红——邻居里不能已有红
            color[u] = 1
            paint(u + 1)
            color[u] = 0                  # 撤销
    paint(1)
    return count

assert count_red_black(3, [(1, 2), (2, 3)]) == 5
assert count_red_black(3, [(1, 2), (2, 3), (1, 3)]) == 4
assert count_red_black(3, []) == 8
assert count_red_black(4, [(1, 2), (2, 3), (3, 4), (4, 1)]) == 7   # 四点环：0 红 1 种 + 1 红 4 种 + 2 红（对角）2 种
assert count_red_black(1, []) == 2

五条断言覆盖：链、三角形、无边、四点环、单点。撤销那一行删掉后第一条断言就会失败（得到 4）。