【原创】古堡深梯探险

题目背景

在一座古老而幽深的古堡中，矗立着一座无尽回旋的阶梯。每层的台阶布局完全相同，许多位置早已断裂塌陷，无法立足。一位冒险者从高层出发，仅携带有限的体力与生命值，试图穿越层层阶梯，抵达古堡最底层的出口。

阶梯之中暗藏规则：盲目回跳会极大消耗体力，笔直下落会承受额外损耗，在同一层徘徊过久则会陷入险境。只有合理规划每一次跳跃，才能在资源耗尽前成功抵达终点。

题目描述

冒险者从第 N 层出发，初始体力为 A，生命值为 B。

楼梯每 M 行为一层，所有楼层结构完全相同。每行有 5 个位置，1 代表可站立的台阶，0 代表无法落脚的虚空。

行从上至下编号。

- 从某一层最后一行向下跳跃1行，将到达下一层第一行。

- 从一层第一行向上跳跃1行，将到达上一层最后一行。

初始位置：当前层第一行最左侧的可站立台阶。

目标：到达第 1 层的最后一行的任意可站立台阶。

冒险者可以在任意两个合法台阶之间直接跳跃，无需逐行移动。

消耗规则

1. 向下跳跃

- 基础消耗 1 点体力。

- 若一次向下跳跃跨越 k 行，则额外消耗 k-1 点生命值。

- 一次跳跃跨越 t 层，体力消耗增加 0.5t，结果向上取整。

2. 同行移动

- 若在同一行内跳跃，共跨越 d 列，则额外消耗 d-1 点体力。

- 连续 3 次及以上仅在同行内移动，每次额外消耗 2 点体力。

3. 同列向下跳跃

- 向下跳跃且落点与起点同列，每跨越一层，额外消耗 1 体力与 1 生命值。

- 连续两次同列向下跳跃，第二次额外消耗 3 点生命值。

4. 向上回跳

- 单次最多向上跳跃 3 行。

- 每向上一行消耗 2 点体力。

- 全局最多向上跳跃 7 次。

- 向上跳跃后，接下来两次向下跳跃的消耗翻倍。

5. 环境损耗

- 每下降一层，生命值自动减 1（第 3 层及以下不再衰减）。

- 连续 5 次跳跃后，所在层数均未严格小于跳跃前层数，直接判定探险失败。

终止条件

满足任一条件时，冒险者立即停止跳跃：

- 体力 \le 0 或 生命值 \le 0

- 向上回跳次数用尽

- 触发连续无效探索判定

- 总跳跃次数 \ge 5N

输入格式

第一行四个整数 N,A,B,M。

接下来 M 行，每行 5 个整数 0/1。

输出格式

- 若能到达目标，输出  Yes 。

- 否则输出  No  与最终所在层数，空格隔开。

数据范围

- 10 ≤N ≤10^5

- 1 ≤A,B ≤5＊10^3

- 5 ≤ M ≤30

- 不保证每行存在台阶

样例输入

12 50 40 5

0 1 0 0 0

1 0 0 0 0

0 0 0 0 0

0 0 1 0 1

1 0 0 0 1

 

样例输出

Yes

提示

1. 本题本质是带资源限制的最短路问题，建议使用优先队列（Dijkstra）进行状态扩展，保证先访问资源更充足的状态。

​

2. 由于层数可达 10^5，不能对每一层单独存储状态，应利用楼层结构完全相同的周期性，仅对「当前层内位置 + 剩余体力 + 剩余生命值」做最优剪枝。

​

3. 需维护每个位置的帕累托最优状态集：若到达同一行、列时，已有状态的体力与生命值均不低于当前状态，则当前状态可直接剪枝，避免指数级爆炸。