图论练习笔记

P1606 [USACO07FEB] Lilypad Pond G

首先跳的过程肯定不会经过相同位置，所以之前经过的位置可以视为原状态，所以可以把添加的莲花数量视为当前路径长度，问题也就转化成了最短路计数。

因为求的是添加莲花的方案数而不是经过路径的方案数，所以可以把已有的莲花连通块缩起来，以水格子为状态进行转移。当然我们并不需要显式地缩，只需要从每个水格子出发 DFS，经过若干莲花格子到达另外一些水格子，然后在它们之间建立一条长度为 \(1\) 的边，表示需要在终点的水格子处添加莲花。

因为边长只有 \(1\)，所以使用 BFS 即可，注意要将起点和终点都视为水格子然后最终长度减一。