# 网格生存概率: 补充解法

贡献：Codex（GPT-6）将网格道路压缩为稀疏图，以道路数控制每轮递推。路径计数和模归一化的完整依据见[网格递推题解](solution.zh.md)。

## 只给道路编号

逐行读入网格，只为字符一建立顶点。保存上一行各列的道路编号和当前行左侧编号；读到道路时，连接已有的上方与左侧道路，并在两个方向登记邻居。坑洞将对应编号重置为空。这样每个无向邻接只在第一次遇到时建立一次，不必保存整个网格或全尺寸编号矩阵。

令道路数为 $V$ .每个顶点最多四个邻居，初始计数为一。每轮对全部道路求其邻居上一轮计数之和，使用两个数组滚动，最后求和并除以 $nm\cdot4^k$ .分母仍包含全部格子，不能改成道路数，因为起点可能落在坑洞。

## 正确性

编号映射恰好保留所有道路和道路间的一步合法移动。每条全程安全的网格路径与图上的一条同长度走法一一对应。初始每个道路计数一，按最后一步分类的递推保持这个对应，所以最终计数等于安全过程数。图中不存在越界或坑洞顶点，自然不会计入失败过程。无道路时数组为空，总数为零；孤立道路在零步有一次过程，正步数的计数为零。

## 代价和适用形状

仍令 $B=\lceil\log_2 P\rceil$ .建图需 $O(nm)$ 时间，每轮 $O(V)$ ，整体时间为 $O(nm+kV+B^2)$ ，空间 $O(V+m)$ ，包含上一行编号和当前输入行。两个计数数组保留精确值，每项不超过 $2^{50}$ ；模运算使用与首选方案相同的防溢出方法。

道路稀少时，每轮跳过大量坑洞；道路密集时，需要额外邻接存储，并不保证优于网格扫描。两者并列适用于完整范围，标准程序选用无需建图的原网格递推。程序见 [alternative.cpp](alternative.cpp)。