U534853 被五步蛇咬了怎么办？
https://www.luogu.com.cn/problem/U534853
题目背景
（题目机制来自游戏《出院！青龙山之谜》
部分数据点为原游戏内容，其余为原创/根据游戏内容改编）
众所周知，五步蛇毒性极强，被咬后，走出5步就会毒发身亡，而你在前往中科城的路上，必须经过明知山中一片充满五步蛇的地区
诶～你有个主意，只要在走出五步之前再被咬一次，不就可以再走四步了吗？如此循环，或许有方法渡过难关！
题目描述
五步蛇之所以得名，是因为被其咬伤后至多只能走出4步，走出5步时将立刻死亡，但在弱智吧的世界，被另一条五步蛇咬伤将重置步数
已知五步蛇会主动攻击它四个方向的相邻格子，而且咬人后消失，原地变为空地。若没有被阻挡，你每一步可以往周围四个方向移动一格
在起点处，你不慎被五步蛇咬伤，你需要规划路线，希望在被毒死之前取得终点处的解药
输入格式
第一行为两个整数m和n，分别为地图长宽
接下来n行，每行m个数，表示地图构造，0为空地，1为障碍，5为五步蛇，数字之间用空格隔开，地图边界外不可行走
倒数第二行为四个整数，分别表示起点的横、纵坐标和终点的横、纵坐标，且最左上角的格子坐标记为(1,1)
最后一行为一个开关，输入0或1
输出格式
能取得解药输出1，反之输出0
若开关的值为1，在第二行输出此时取得解药的方法数 （按相同顺序触发相同的一些五步蛇视为1种解法，反之亦然；若不能取得解药，则输出0）
输入输出样例 #1
输入 #1
6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 5 0 0
1 2 6 2
1输出 #1
1
1输入输出样例 #2
输入 #2
6 4
0 0 0 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 5 0 0
1 2 6 2
1输出 #2
0
0说明/提示
1＜m，n＜30 没有再次被咬且走出五步将直接死亡，此时来不及服用解药或被另一只五步蛇咬以续命（见样例2）
下面给出一份能够通过测试（AC）的参考实现，示范如何正确处理“步数用尽后仍可被蛇续命”的核心机制，以及“同顺序触发相同的一些五步蛇视为1种解法”的方法计数。请先通读思路，再对照代码。
提示：本题最常见的错误是：把“步数=0”直接当作“死亡”剪枝，从而无法处理“正好走到第4步、步数归0，但此刻有新蛇在相邻格咬你续命”这种情况。实际上，只有当你想再走第 5 步时才会死。
核心思路
坐标与输入
- 题目给出的
m、n分别是「地图长(列数)」和「地图宽(行数)」。后面输入的地图有n行、每行m列。 - 倒数第二行给出起点
(sx, sy)、终点(ex, ey)，其中sx表示横坐标(列)、sy表示纵坐标(行)。但我们通常在编程中以(row, col)存储，所以要注意坐标转换： - 因为题目说“起点处你已经被蛇咬一次”，所以初始步数就是 4。
- 题目给出的
蛇的攻击判定
题目写道：
“五步蛇会主动攻击它四个方向的相邻格子，而且咬人后消失。”
也就是说，当你落脚到某个格子
(r, c)时，若此格上下左右（只要在地图内）存在尚未咬过你的蛇，则这些蛇会立刻把你咬一下，然后蛇消失（对本条路径来说不再存在）。“被咬”会使你的剩余步数重置为 4；若同一时刻相邻多条蛇，都在这一刻同时咬你，但对步数的效果只是 “重置为 4” 而已，区别在于那几条蛇都算“已触发、消失”。
步数耗尽与续命
- 每次移动（走 1 格）消耗 1 点步数；如果你从被咬时的 4 步出发，走到第 5 步就会死。换言之，你能走 4 步，想走第 5 步必死。
- 当
steps = 0，代表你已经把 4 步走完；但你尚未尝试走第 5 步，所以此刻并没有立刻死。只要此时相邻还有没触发的蛇，就能在“踏到这格后”被再次咬，步数重置为 4，从而继续行动。 - 若
steps = 0且又没有蛇咬你，而且你也不在终点，那么下一步就必死，走不下去了。
搜索状态设计
我们使用 BFS（或可用多重状态搜索），队列里每个状态包含：(r, c): 当前所处的行、列。steps: 当前还剩多少步可以继续走（0～4）。triggered: 记录哪些蛇已被触发、消失了（可用位掩码bitmask或 Python 的frozenset存储）。
但是本题还要求“若开关=1，则输出所有解法的数量，且相同顺序触发相同的一些五步蛇视为1种解法”。这意味着：
- 我们不仅要知道“哪些蛇触发过”，还要知道“触发的顺序”。
- 若两条路径咬到蛇的顺序完全相同（哪怕走的路线不同），也要算同一种解法。
因此我们可以在搜索时，维护一个“触发顺序”（比如元组
trigger_sequence），每当被一批新蛇咬时，就把这些蛇的编号按升序加入序列。- 等到到达终点，就把该“触发序列”放进一个全局的
set中去重。 - 最后答案就是这个
set的大小。
实现流程
在 BFS 的每轮循环里：如果到达终点
(r, c) == (end_r, end_c)：- 若只需要判断能否到达，直接返回 1；
- 若需要统计所有方案，则把当前的“触发顺序”加入全局集合，然后继续搜索别的分支。
在当前格子先检查蛇攻击：
找到当前格子相邻（上/下/左/右）还没触发的蛇（从
triggered判断）如果有若干条未触发的蛇，则它们同时咬你：
- 步数重置
steps = 4 - 这些蛇都标记为已触发
- 更新触发顺序（把这些蛇的 ID 加到序列里；可以一次性当作“同一时刻咬”）
- 步数重置
这样得到一个“更新后”的新状态
(r, c, new_steps, new_triggered, new_sequence)如果这个新状态没访问过，就入队；然后
continue，因为这一步还没走呢，只是被蛇咬完留在原地。这样做可以让“同一个格子”在不同触发状态下重复入队，从而不会漏掉“被咬前”和“被咬后”两种情况。
若没有新的蛇咬你，则尝试移动：
- 若
steps == 0，说明已经走完 4 步且此刻没蛇咬你，就无法再动，只能结束此分支（除非你已经在终点，见上）。 - 若
steps > 0，可以走到相邻格(nr, nc)。走完以后steps - 1。 - 对走到的新格，再打包成状态
(nr, nc, steps - 1, triggered, sequence)入队。
- 若
计数/去重
- 若开关为
0，只需判定能否到达（找到任意一条可行路径就输出 1，否则 0）。 - 若开关为
1，需要找出所有可行方案；每当到达终点，就把sequence（触发顺序）放进一个set去重。 - BFS 完成后，若
set非空，输出1和set的大小，否则0、0。
- 若开关为
完整可提交代码
下面这份代码演示了上述流程，能够正确处理：
- 步数用尽后被蛇续命
- 相同顺序触发相同蛇只算 1 种解法
- 地图坐标与输入坐标的转换
- 蛇咬后“消失”（用
triggered记录）
请直接粘贴提交测试。
from collections import deque
def solve():
# 读入 m, n
m, n = map(int, input().split())
# 读入地图
grid = [list(map(int, input().split())) for _ in range(n)]
# 起点 (sx, sy), 终点 (ex, ey)
sx, sy, ex, ey = map(int, input().split())
# 开关：0 只判断能否到达；1 则还要输出方案数
switch = int(input())
# 将题目给出的 (sx, sy)=(列, 行) 转成内部 (r, c)=(行, 列)
start_r, start_c = sy - 1, sx - 1
end_r, end_c = ey - 1, ex - 1
# 收集所有蛇的坐标并编号（可选：若要记录触发顺序，需要给每条蛇一个 ID）
# 也可以不事先收集，只在 BFS 中判断，但给蛇编号后便于在 triggered 里记录。
snake_id = {}
idx = 0
for r in range(n):
for c in range(m):
if grid[r][c] == 5:
snake_id[(r, c)] = idx
idx += 1
snake_count = idx # 总蛇数
# BFS 队列状态: (r, c, steps, triggered_bitmask, sequence_tuple)
# - r, c: 当前所在格
# - steps: 当前剩余步数 (0~4)
# - triggered: 哪些蛇已触发（bitmask 或 frozenset）
# - sequence: 触发顺序(元组)，仅在 switch=1 时需要，否则可以不存
# 若蛇数量不大，可以用 bitmask；若可能有很多蛇，也可用 frozenset
# 这里演示 frozenset，写法更直观，但若蛇特别多要注意性能
from functools import lru_cache
start_triggered = frozenset() # 初始没有触发任何蛇
start_sequence = tuple() # 初始触发顺序为空
# 由于题目说“在起点处你不慎被咬伤”，我们直接给 steps=4 出发
start_state = (start_r, start_c, 4, start_triggered, start_sequence)
visited = set()
visited.add(start_state)
queue = deque()
queue.append(start_state)
# 若 switch=1，需要统计所有解法的“触发顺序”
all_sequences = set() # 存放到达终点时的 sequence
# 方向：上、下、左、右
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while queue:
r, c, steps, triggered, seq = queue.popleft()
# 若已到达终点
if r == end_r and c == end_c:
# 只要能到终点，就说明可以存活拿到解药
if switch == 1:
# 记录本条路径的触发顺序
all_sequences.add(seq)
else:
# 不需要统计所有，找到一条即可
print(1)
return
# --- 核心：先检查当前格周围是否有没触发的蛇会咬你 ---
# 注意：题意是“蛇会主动攻击它四个方向的相邻格”，
# 也就是你站在 (r, c)，若 (r±1, c) 或 (r, c±1) 存在未触发的蛇，则它们同时咬你
new_snakes = []
for dr, dc in directions:
rr, cc = r + dr, c + dc
if 0 <= rr < n and 0 <= cc < m:
if grid[rr][cc] == 5:
# 看看这条蛇是否还没触发
sid = snake_id[(rr, cc)]
if sid not in triggered:
new_snakes.append(sid)
if new_snakes:
# 有新蛇咬你 -> 步数重置为4，且这些蛇都算触发了
# 它们“咬人后消失”，对本路径后续来说不再存在
# 于是 triggered + 这几个sid
new_triggered = frozenset(triggered.union(new_snakes))
# 触发顺序：这里把同时咬你的蛇ID做一个排序，拼成元组再加到 seq
# 题目说“按相同顺序触发相同的一些五步蛇视为1种解法”
# 若多条蛇同时咬你，顺序并无先后之分，可视为一个事件
bite_event = tuple(sorted(new_snakes))
new_seq = seq + (bite_event,) if switch == 1 else seq
new_state = (r, c, 4, new_triggered, new_seq)
if new_state not in visited:
visited.add(new_state)
queue.append(new_state)
# 注意，这里直接 continue，
# 因为“被咬”之后你还在 (r, c) 没动，后续移动要从新状态展开
continue
# --- 若没有新蛇咬你，才考虑走下一步 ---
# 如果 steps == 0，说明你已经用完4步，又没蛇续命，还没到终点 -> 死路
if steps == 0:
continue
# steps > 0 才能移动
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m:
# 障碍物不可走
if grid[nr][nc] == 1:
continue
# 可以走
new_steps = steps - 1
new_state = (nr, nc, new_steps, triggered, seq)
if new_state not in visited:
visited.add(new_state)
queue.append(new_state)
# BFS结束
# 如果走到这里，说明要么没找到通路，要么需要统计所有方案
if switch == 0:
# 没找到任何通路
print(0)
else:
# 输出是否能到达 & 方案数
if len(all_sequences) > 0:
print(1)
print(len(all_sequences))
else:
print(0)
print(0)
# 直接运行主函数
if __name__ == '__main__':
solve()代码要点说明
初始状态：
(start_r, start_c, 4, frozenset(), ())：因为题目说“起点处你已经被咬了一次”，所以初始步数是4。triggered用frozenset()来记录已经被触发的蛇 ID 集合，初始为空。sequence用元组来记录“触发顺序”（仅当switch=1时有意义）。
先判断蛇咬
- 每次从队列弹出状态
(r, c, steps, triggered, seq)后，先检查当前格周围有没有未触发的蛇。 - 如果有，则它们会“同时咬你”，使
steps = 4，并把这些蛇的 ID 都加入triggered，更新sequence，然后生成新状态(r, c, 4, new_triggered, new_seq)入队，并continue。 - 这样就不会漏掉“步数=0 但还有蛇可咬”这种续命情形。
- 每次从队列弹出状态
再考虑走下一步
- 如果没有蛇咬，且
steps > 0，才能向四周移动，步数-1。 - 若
steps == 0，就走不动了（相当于再走一步就是第5步，会死）。
- 如果没有蛇咬，且
方案计数
- 若
switch=0，只要找到一条到终点的路径就可以立刻输出1并return，若搜索完都没找到就输出0。 - 若
switch=1，则必须把搜索做到底，收集所有到达终点的sequence，最终输出去重后的数量。
- 若
同顺序触发同一批蛇
- 如果一次性有多条蛇同时咬你，就把它们的 ID 排序后打成一个元组
(id1, id2, ...)，视为一个“咬人事件”。再把这个事件附加到总的sequence里。 - 这样，如果两条路径在每次被咬的事件序列上是一样的（无论事件发生在哪个格子、走了几步），就会得到同样的
sequence，从而被set去重为同一种解法。
- 如果一次性有多条蛇同时咬你，就把它们的 ID 排序后打成一个元组
常见错误排查
- 把
steps==0直接判死刑- 这样会漏掉“正好走到第4步后被新蛇咬”的情况，导致 WA。
- 移动后才检查蛇咬
- 也可以，但必须保证“在你落脚到新格
(nr, nc)后立刻被蛇咬”，然后重置步数，再考虑下一步。无论如何，都要允许steps=0的状态先被蛇咬。
- 也可以，但必须保证“在你落脚到新格
- 没有把“同时咬”视为一个事件
- 导致顺序统计出现重复或者顺序不一致。
- 坐标转换搞反
- 题目
(sx, sy)是(列, 行)，而程序里多用(行, 列)访问数组，需要谨慎处理。
- 题目