1. 问题分析

我们有一个：

• R × C 的网格，每个格子有数字 0~8（0 表示不可进入）。
• 初始蛇长度为 4，给定初始 4 节身体的坐标。
• 有 N ≤ 4 个食物，分布在不同的可进入格子上。
• 蛇可以朝 L、R、U、D 四个方向移动或进食。
• 移动：头移到相邻格（非 0），并且新位置不在当前身体的除尾部以外的任何一节，身体整体前移一节（尾部消失一节）。
• 进食：新头位置有食物且没被吃过，身体增长一节（保留原尾部）。
• 时间花费：移动或进食时间 = |w(旧头) - w(新头)| + 1。
• 目标：吃完所有食物（吃到即消失，每个食物只一次）的最短时间，并输出路径。

2. 状态表示

因为 N ≤ 4，可以用状态压缩表示哪些食物已吃：用一个 bitmask（整数 0 ~ 2^N-1）。

但蛇的身体会变长，而且必须判断是否会撞到自己，所以状态里除了：

• 蛇头位置 (x, y)
• 已吃食物掩码 eaten
• 当前时间 time
• 路径 path

还需要表示蛇的身体，以便做碰撞检测。

2.1 身体表示方法

直接存储整个身体的坐标列表会很大，但注意到：

• 初始长度 4，最多吃到 N 个食物，所以最大长度 = 4 + N ≤ 8。
• 身体相邻两节总是上下左右相邻。
• 因此可以用相对位置链来表示身体：例如，从头部开始，记录每一节相对于前一节的方向（4 种可能），这样长度为 L 的身体只需 L-1 个方向数据。

但更简单的做法是：因为 R、C ≤ 12，且 L ≤ 8，直接存储整个身体坐标列表（长度 L ≤ 8）作为状态的一部分，状态数不会太大。

2.2 状态判重

状态 = (head_x, head_y, eaten_mask, body_coords_list)
为了判重，可以用 (head_x, head_y, eaten_mask, body_shape) 作为 key，其中 body_shape 可以用相对坐标序列的哈希或直接整个坐标列表的元组化。

BFS 时，如果同一状态之前以更短时间到达过，则剪枝。

3. 搜索过程

用 优先队列（Dijkstra） 因为每次移动时间不一定相同（不是步数一致）。

1. 初始状态：蛇初始位置，eaten_mask = 0，时间 0，路径空。
2. 每次从队列取出时间最小的状态。
3. 如果 eaten_mask == (1<<N)-1，则找到解，输出时间和路径。
4. 否则，枚举 4 个方向，计算新头位置。
5. 检查边界、格子非 0、不撞身体（除了尾部）。
6. 判断是否吃到新食物：
   • 如果吃到且该食物未吃过，则 new_mask = old_mask | (1<<food_index)，身体增长（保留原身体全部，新头插入前面）。
   • 如果没吃到，身体前移（去掉尾部）。
7. 计算时间花费：|grid[old_x][old_y] - grid[new_x][new_y]| + 1。
8. 新状态若未访问过或时间更短，则入队。

4. 优化

• 身体碰撞检测时，注意规则允许新头移动到旧尾部位置，因为移动后尾部会前移，不再重叠。
• 状态编码可以用字符串或元组，用于 map 或 unordered_map 判重。
• 因为 N 很小，且 R、C 小，状态数 = (R×C) × (2^N) × (身体形状数)，身体形状数不会太大（因为长度 ≤ 8，且必须连通），所以 BFS 可行。
• 如果超时，可以尝试用 IDA* 不太合适，因为时间不是步数，而且状态复杂。保持 Dijkstra 即可。

5. 总结

这道题是一个典型的状态搜索问题，难点在于：

1. 正确表示蛇的身体状态；
2. 处理移动与进食时身体的变化；
3. 判断合法移动时注意尾部特殊情况；
4. 状态空间较大，需要高效编码与去重。

只要正确实现 BFS/Dijkstra 状态转移和身体更新，就能在给定数据范围内求解。