T30193: 哈密顿激活层
DFS+剪枝, http://cs101.openjudge.cn/practice/30193/
"Dead neurons tell no tales." "死去的神经元不会说话。" —— 2077年《荒坂技术内刊》
在代号为 "DeepMind-X" 的下一代神经网络架构中，架构组提出了一种革命性的 “哈密顿激活层”。
HAL 是一个 N × M 的神经元矩阵（最多10x10）。但在制造过程中，由于量子隧穿效应，部分神经元变成了 “坏死区”，无法传递信号。为了保证梯度的无损传播，激活信号必须遵循极其严苛的物理法则：
- 全覆盖： 信号必须从输入神经元（强度为 1）出发，恰好激活矩阵中的每一个正常神经元一次。不能经过坏死区，也不能重复激活或遗漏任何正常神经元。
- 邻域传递： 信号只能在网格中向上下左右（4 联通）相邻的正常神经元传递。
- 时序同步： 为了与其他层并行计算，矩阵中有 K 个关键神经元被标记了固定的时间戳。这意味着信号必须在第 t 步精确到达该位置。
作为首席架构师，你需要编写核心驱动，计算出激活信号的完整传递路径。
输入
第一行包含四个整数 N, M, K, B，分别表示矩阵的行数、列数、被锁定的关键神经元数量、以及障碍物（坏死区）的数量。 接下来 K 行，每行三个整数 r, c, t，表示坐标为 (r, c) 的神经元必须在第 t 步被激活。输入保证包含起点信息（即存在一行满足 t=1）。 1 ≤ t ≤ N × M − B。 接下来 B 行，每行两个整数 r, c，表示坐标 (r, c) 是坏死区，无法通行。 坐标 (r, c) 从 1 开始，1 ≤ r ≤ N, 1 ≤ c ≤ M。 保证障碍物坐标与关键神经元坐标不重叠。
输出
如果存在可行的激活方案，输出 N × M − B 行（即路径的总长度）。第 i 行包含两个整数 r_i,c_i，表示路径中第 i 步经过的神经元坐标。 如果存在多种方案，输出任意一种即可。 如果不存在可行方案，输出 -1。
样例输入
3 3 2 1
1 1 1
3 3 8
2 2样例输出
-1提示
DFS+剪枝
来源
TA-xjk
【魏佳亮 24物院】思路：剪枝思路就是不能提前占坑+不能和未来要到的点距离太远（超过时间差）
另外一个剪枝：奇偶性剪枝 (Parity Pruning)。例如，如果离目标点还有 3 格距离（曼哈顿），但必须要 4 步之后到达，这是绝对不可能的。因为在网格中每走一步，坐标和 x+y 的奇偶性就会翻转一次。距离差与时间差必须同奇偶。
python
import sys
# 增加递归深度，防止深搜爆栈
sys.setrecursionlimit(2000)
def solve():
N, M, K, B = map(int, input().split())
targets = []
start_pos = None
w = []
grid = [[0] * M for _ in range(N)]
for _ in range(K):
r, c, t = map(int, input().split())
if t == 1:
start_pos = (r - 1, c - 1)
targets.append((r - 1, c - 1, t))
# 按时间排序关键点，方便后续剪枝逻辑
targets.sort()
for _ in range(B):
r, c = map(int, input().split())
grid[r - 1][c - 1] = -1
# 路径总长度
total_steps = N * M - B
# 记录路径: path[t-1] = (r, c)
path = [(0, 0)] * total_steps
# 方向数组
dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]
def dfs(x, y, t):
# 记录路径
path[t - 1] = (x + 1, y + 1)
if t == total_steps:
return True
for dx, dy in dirs:
nx, ny = x + dx, y + dy
nt = t + 1
if 0 <= nx < N and 0 <= ny < M and not grid[nx][ny]:
is_valid_step = True
for i, j, target_t in targets:
dist = abs(nx - i) + abs(ny - j)
remain_time = target_t - nt
if target_t < nt:
continue
# 核心剪枝逻辑
# A. 距离太远，时间不够
# B. 奇偶性不符 (剩余时间 - 距离 必须是偶数)
if dist > remain_time :
is_valid_step = False
break
# C. 不能提前占用未来的关键点
if nx == i and ny == j and target_t != nt: # 踩了关键点坐标
is_valid_step = False
break
if is_valid_step:
grid[nx][ny] = -1
if dfs(nx, ny, t + 1):
return True
grid[x + dx][y + dy] = 0 # 回溯
return False
sx, sy = start_pos
grid[sx][sy] = -1 # 起点标记为已访问
if dfs(sx, sy, 1):
for r, c in path:
print(r, c)
else:
print(-1)
if __name__ == "__main__":
solve()python
import sys
# 增加递归深度上限，防止大规模网格搜索时栈溢出
sys.setrecursionlimit(20000)
def solve():
# 使用一次性读取所有输入，提高IO效率
input_data = sys.stdin.read().split()
if not input_data:
return
iterator = iter(input_data)
try:
N = int(next(iterator))
M = int(next(iterator))
K = int(next(iterator))
B = int(next(iterator))
except StopIteration:
return
# 构建坐标与时间的双向映射
coord_to_time = {}
time_to_coord = {}
# 读取关键点
for _ in range(K):
r = int(next(iterator)) - 1
c = int(next(iterator)) - 1
t = int(next(iterator))
coord_to_time[(r, c)] = t
time_to_coord[t] = (r, c)
# 初始化网格：0表示空，-1表示障碍，1表示已访问
grid = [[0] * M for _ in range(N)]
for _ in range(B):
r = int(next(iterator)) - 1
c = int(next(iterator)) - 1
grid[r][c] = -1 # 标记障碍物
total_steps = N * M - B
# 确定起点
if 1 in time_to_coord:
start_r, start_c = time_to_coord[1]
else:
# 题目保证存在 t=1，防御性编程
print("-1")
return
# 标记起点已访问
grid[start_r][start_c] = 1
# 用于记录路径
path = [(0, 0)] * (total_steps + 1)
path[1] = (start_r, start_c)
# 将关键点按时间排序，方便查找下一个目标
sorted_checkpoints = sorted(time_to_coord.items())
# 【剪枝 1】全局可行性预判：相邻关键点之间的距离和奇偶性校验
for i in range(len(sorted_checkpoints) - 1):
t1, (r1, c1) = sorted_checkpoints[i]
t2, (r2, c2) = sorted_checkpoints[i + 1]
dist = abs(r1 - r2) + abs(c1 - c2)
dt = t2 - t1
# 距离太远无法到达，或奇偶性不符（必须同奇偶）
if dist > dt or (dt - dist) % 2 != 0:
print("-1")
return
# 方向数组：上、下、左、右
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# 辅助函数：计算某格子的动态度数（可行邻居数量）
def get_degree(r, c):
d = 0
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < N and 0 <= nc < M and grid[nr][nc] == 0:
d += 1
return d
# DFS 函数
# r, c: 当前坐标
# step: 当前步数
# cp_idx: 当前关注的关键点在 sorted_checkpoints 中的索引
def dfs(r, c, step, cp_idx):
# Base Case: 走完所有步数，成功
if step == total_steps:
return True
next_step = step + 1
# 确定下一个必须要到达的目标关键点
# 如果当前步数已经到达或超过了 cp_idx 指向的关键点，则关注下一个
cur_t, cur_pos = sorted_checkpoints[cp_idx]
target_t, target_pos = -1, None
new_cp_idx = cp_idx
if cur_t == step:
# 当前正好是关键点，目标切换为下一个
if cp_idx + 1 < len(sorted_checkpoints):
new_cp_idx = cp_idx + 1
target_t, target_pos = sorted_checkpoints[new_cp_idx]
else:
# 后面没有显式关键点了
target_t = -1
else:
# 还没到当前关注的关键点，目标依旧是它
target_t, target_pos = cur_t, cur_pos
# 【剪枝 2】曼哈顿距离剪枝 (针对当前位置到下一个关键点)
if target_t != -1:
tr, tc = target_pos
dist = abs(r - tr) + abs(c - tc)
rem_time = target_t - step
# 如果剩余时间不够走直线距离，或者奇偶性不对，回溯
if dist > rem_time or (rem_time - dist) % 2 != 0:
return False
# 生成候选邻居
candidates = []
for dr, dc in directions:
nr, nc = r + dr, c + dc
# 越界检查
if not (0 <= nr < N and 0 <= nc < M):
continue
# 访问检查（含障碍物）
if grid[nr][nc] != 0:
continue
# 【约束检查 1】如果该邻居是某个关键点，必须时间吻合
if (nr, nc) in coord_to_time:
if coord_to_time[(nr, nc)] != next_step:
continue # 该位置被预留给未来，现在不能踩
# 【约束检查 2】如果下一时刻规定了必须去某处，必须吻合
if next_step in time_to_coord:
if time_to_coord[next_step] != (nr, nc):
continue # 违背了下一步的强制规定
# 计算启发式分数
# 1. 度数 (Warnsdorff's Rule): 越小越好，优先填死角
deg = get_degree(nr, nc)
# 2. 距离分: 离目标越近越好
dist_score = 0
if target_t != -1:
tr, tc = target_pos
dist_score = abs(nr - tr) + abs(c - tc)
candidates.append((deg, dist_score, nr, nc))
# 【核心策略】排序候选者
# 优先度数小 (deg)，其次距离近 (dist_score)
# 这能有效避免在非目标区域形成孤岛
candidates.sort(key=lambda x: (x[0], x[1]))
for _, _, nr, nc in candidates:
# 标记访问
grid[nr][nc] = 1
path[next_step] = (nr, nc)
# 递归
if dfs(nr, nc, next_step, new_cp_idx):
return True
# 回溯
grid[nr][nc] = 0
# path[next_step] 不需要清除，会被覆盖
return False
# 启动 DFS，初始关注第0个关键点(即起点)
if dfs(start_r, start_c, 1, 0):
# 输出结果，转回 1-based 坐标
for i in range(1, total_steps + 1):
print(f"{path[i][0] + 1} {path[i][1] + 1}")
else:
print("-1")
if __name__ == "__main__":
solve()这是一个非常经典的哈密顿路径（Hamiltonian Path）问题变种。在一个网格图中寻找一条经过所有非障碍点恰好一次的路径，本身是一个 NP-完全（NP-Complete） 问题。但是，题目给出的数据范围较小（
，且通常 较小，最大 10），并且增加了许多强约束（关键点必须在特定时间到达），这使得我们可以使用 DFS（深度优先搜索） + 强剪枝 来解决。 以下是对该解题思路和代码的详细解读。
一、 核心解题思路
1. 问题建模
我们需要在一个网格中填入数字
到 （ 为非障碍格子的总数），使得：
填在起点。 - 数字
和 的位置相邻。 - 特定位置必须填入特定的数字（关键点约束）。
- 所有非障碍格子都被填满。
2. 算法选择：DFS（回溯法）
由于需要找一条完整路径，BFS 不适用（状态空间太大且难以记录路径），只能使用 DFS 进行回溯搜索。
3. 关键剪枝策略（这是通过此题的关键）
如果没有剪枝，搜索空间是指数级的，肯定会超时。代码中应用了以下核心策略：
可行性预判（全局剪枝）： 在开始搜索前，检查所有关键点之间是否矛盾。
- 曼哈顿距离约束：如果关键点 A (时间
) 和关键点 B (时间 ) 之间的曼哈顿距离 ，则物理上无法到达，直接返回 -1。 - 奇偶性约束（Parity Check）：在网格图中，每走一步，坐标
的奇偶性就会改变一次。因此，两点间的步数差 和曼哈顿距离 必须同奇同偶。即 (dt - dist) % 2 == 0。如果不满足，直接返回 -1。过程中的可行性剪枝（局部剪枝）： 在 DFS 过程中，时刻计算当前位置到下一个目标关键点的距离。如果当前步数加上最短距离已经超过了关键点规定的时间，或者奇偶性不符，立即回溯。
强预留约束：
- 如果邻居格子是未来的某个关键点（时间
），而当前步数并非 ，则绝对不能提前踩入该格子。 - 如果下一步（
）是某个关键点的时间，那么必须且只能走向那个关键点。 启发式搜索顺序（Warnsdorff's Rule / 度数优先）： 这是代码中最精妙的部分。在选择下一步走哪里时，不是随便选，而是对候选邻居进行排序：
- 优先度数（Degree）小：优先走那些“路比较少”的格子。比如一个角上的格子，如果现在不去，以后可能就被堵死进不去了。这能极大地减少产生“孤岛”的概率。
- 次优先距离目标近：在度数相同的情况下，优先向下一个关键点靠拢。
二、 代码详细解读
1. 准备工作与输入处理
pythonimport sys # 增加递归深度，防止 10x10 全图遍历时爆栈 sys.setrecursionlimit(20000) def solve(): # 使用 sys.stdin.read 一次性读取，比 input() 快很多 input_data = sys.stdin.read().split() # ... (迭代器解析 N, M, K, B) ...2. 数据结构映射
python# 建立双向映射，方便 O(1) 查询 coord_to_time = {} # (r,c) -> t: 判断某位置是否是关键点 time_to_coord = {} # t -> (r,c): 判断某时刻是否必须去某地 # ... (读取关键点并填充映射) ... # 网格初始化：-1 障碍, 0 空, 1 已访问 grid = [[0] * M for _ in range(N)] # ... (标记障碍物为 -1) ...3. 全局可行性检查 (剪枝 1)
python# 将关键点按时间排序 sorted_checkpoints = sorted(time_to_coord.items()) # 检查每两个相邻的关键点是否可达 for i in range(len(sorted_checkpoints) - 1): t1, (r1, c1) = sorted_checkpoints[i] t2, (r2, c2) = sorted_checkpoints[i + 1] dist = abs(r1 - r2) + abs(c1 - c2) # 曼哈顿距离 dt = t2 - t1 # 1. 时间不够走直线距离 # 2. 奇偶性不一致 (dt - dist 必须是偶数) if dist > dt or (dt - dist) % 2 != 0: print("-1") return解读：这步非常重要。比如要求第1步在(0,0)，第2步在(0,2)，距离是2但时间差是1，根本走不过去，直接判死刑，避免无效搜索。
4. DFS 函数设计
python# DFS 参数：当前坐标(r,c)，当前步数 step，当前关注的下一个关键点索引 cp_idx def dfs(r, c, step, cp_idx): # Base Case: 填满所有格子，成功 if step == total_steps: return True next_step = step + 1 # --- 确定当前的导航目标 --- # 逻辑：如果已经到达了当前关注的关键点，就切换关注下一个关键点 cur_t, cur_pos = sorted_checkpoints[cp_idx] if cur_t == step: # 切换到下一个关键点 # ... # --- 剪枝 2: 曼哈顿距离剪枝 (针对动态过程) --- if target_t != -1: tr, tc = target_pos dist = abs(r - tr) + abs(c - tc) rem_time = target_t - step # 如果剩余时间不够，或者奇偶性不对，回溯 if dist > rem_time or (rem_time - dist) % 2 != 0: return False5. 候选节点生成与启发式排序 (核心优化)
pythoncandidates = [] for dr, dc in directions: # ... (越界检查、障碍检查、重复访问检查) ... # --- 约束检查 1: 避免提前踩入未来的关键点 --- if (nr, nc) in coord_to_time: if coord_to_time[(nr, nc)] != next_step: continue # --- 约束检查 2: 下一步必须去指定关键点 --- if next_step in time_to_coord: if time_to_coord[next_step] != (nr, nc): continue # --- 启发式打分 --- # get_degree: 计算该邻居周围还有几个空格子可走 deg = get_degree(nr, nc) # dist_score: 离目标的距离 candidates.append((deg, dist_score, nr, nc)) # --- 排序 --- # 优先选择度数小的格子走（Warnsdorff's Rule） # 这样可以先把那些容易变成死角的格子填上 candidates.sort(key=lambda x: (x[0], x[1])) for _, _, nr, nc in candidates: grid[nr][nc] = 1 # 标记 path[next_step] = (nr, nc) # 记录路径 if dfs(nr, nc, next_step, new_cp_idx): # 递归 return True grid[nr][nc] = 0 # 回溯解读 - 为什么按度数排序？ 假设你在走迷宫，面前有两条路 A 和 B。
- A 周围只剩 1 个出口了（度数为1）。
- B 周围还有 3 个出口（度数为3）。 如果你先选了 B，那么 A 可能这辈子都走不到了，因为 A 唯一的出口被你刚才的路过给堵死了（或者你需要绕很大一圈才能回来，但哈密顿路径不能重复走）。 所以，先走那个“快要无路可走”的格子，是哈密顿路径搜索极其重要的启发式规则。
三、 总结
这道题是 搜索算法 的集大成者。
- 基础：DFS 回溯框架。
- 逻辑：处理障碍物、边界、路径记录。
- 剪枝：利用题目特有的“关键点时间戳”进行曼哈顿距离剪枝和奇偶性剪枝。
- 启发式：利用图论中的度数概念优化搜索顺序，极大提高了寻找可行解的效率。
如果没有最后的
candidates.sort启发式排序，代码很可能会在某些复杂数据上超时；如果没有奇偶性检查，会浪费大量时间在不可能的路径上。