📖 答案解析 — 智传民韵（民族文化） — 困难2

from collections import deque
m, n = map(int, input().split())
grid = []
for _ in range(m):
    grid.append(list(map(int, input().split())))
start_x, start_y, end_x, end_y = map(int, input().split())
# 如果起点或终点本身是障碍，无法到达
if grid[start_x][start_y] == 1 or grid[end_x][end_y] == 1:
    print(-1)
else:
    # BFS
    # 四个方向：上、下、左、右
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    # visited数组记录是否访问过
    visited = [[False] * n for _ in range(m)]
    visited[start_x][start_y] = True
    # 队列中存储 (x, y, 步数)
    queue = deque()
    queue.append((start_x, start_y, 0))
    answer = -1
    while queue:
        x, y, steps = queue.popleft()
        # 到达终点
        if x == end_x and y == end_y:
            answer = steps
            break
        # 向四个方向扩展
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            # 检查边界、是否可通行、是否已访问
            if 0 <= nx < m and 0 <= ny < n:
                if grid[nx][ny] == 0 and not visited[nx][ny]:
                    visited[nx][ny] = True
                    queue.append((nx, ny, steps + 1))
    print(answer)

n, M = map(int, input().split())
pools = []
for i in range(n):
    c, h = map(int, input().split())
    pools.append([i + 1, c, h])
# 按单位快乐值降序排序；单位快乐值相同按容量降序
pools.sort(key=lambda x: (-x[2], -x[1]))
remaining = M
total_joy = 0
results = []
for idx, cap, joy in pools:
    if remaining <= 0:
        break
    if cap <= remaining:
        # 加满该水池
        results.append((idx, cap))
        total_joy += cap * joy
        remaining -= cap
    else:
        # 只能加入部分水
        results.append((idx, remaining))
        total_joy += remaining * joy
        remaining = 0
print(total_joy)
for idx, amount in results:
    print(f"水池{idx}: 加入{amount}升")

n, W = map(int, input().split())
weights = [0]
values = [0]
for i in range(1, n + 1):
    w, v = map(int, input().split())
    weights.append(w)
    values.append(v)
# dp[i][j]: 考虑前i件银饰，总重量不超过j时的最大价值
dp = [[0] * (W + 1) for _ in range(n + 1)]
# 记录选择路径：choice[i][j] 表示在考虑前i件、容量为j时是否选择了第i件
choice = [[False] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, W + 1):
        # 不选第i件
        dp[i][j] = dp[i - 1][j]
        # 可以选第i件
        if j >= weights[i]:
            if dp[i - 1][j - weights[i]] + values[i] > dp[i][j]:
                dp[i][j] = dp[i - 1][j - weights[i]] + values[i]
                choice[i][j] = True
print(dp[n][W])
# 回溯找出被选中的银饰编号
selected = []
j = W
for i in range(n, 0, -1):
    if choice[i][j]:
        selected.append(i)
        j -= weights[i]
selected.sort()
print(' '.join(map(str, selected)))

import sys
sys.setrecursionlimit(1000000)
m, n = map(int, input().split())
grid = []
for _ in range(m):
    grid.append(list(map(int, input().split())))
visited = [[False] * n for _ in range(m)]
# 四个方向：上、下、左、右
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def dfs(x, y, color):
    """从(x,y)出发DFS搜索同色连通区域，返回该区域的格子数"""
    count = 1
    visited[x][y] = True
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= nx < m and 0 <= ny < n:
            if not visited[nx][ny] and grid[nx][ny] == color:
                count += dfs(nx, ny, color)
    return count
# BFS版本（备选）
from collections import deque
def bfs(start_x, start_y, color):
    """从(start_x, start_y)出发BFS搜索同色连通区域，返回该区域的格子数"""
    count = 0
    queue = deque()
    queue.append((start_x, start_y))
    visited[start_x][start_y] = True
    while queue:
        x, y = queue.popleft()
        count += 1
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < m and 0 <= ny < n:
                if not visited[nx][ny] and grid[nx][ny] == color:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
    return count
# 遍历整个画布，找出所有连通区域
regions = []  # 存储 (颜色, 格子数)
for i in range(m):
    for j in range(n):
        if grid[i][j] != 0 and not visited[i][j]:
            # 使用DFS
            # region_size = dfs(i, j, grid[i][j])
            # 或使用BFS（任选一种，效果相同）
            region_size = bfs(i, j, grid[i][j])
            regions.append((grid[i][j], region_size))
# 先按颜色值排序，相同颜色按发现的先后顺序（即原始顺序）
regions.sort(key=lambda x: x[0])
print(len(regions))
for color, size in regions:
    print(f"颜色{color}: {size}个格子")