题意简述：有 $n\times m$ 的网格，上面有 $k$ 个障碍物，分别在 $(x_i,y_i)$。起点在 $(1,1)$，终点在 $(n,m)$。每次只能向右走或向下走。即从 $(i,j)$ 可以走到 $(i+1,j)$ 或 $(i,j+1)$，不能回头。问：至少再添加几个障碍物，才能使得不能从起点走到终点？（障碍物不能添加在起点或终点）

范围：$1\le n,m\le3000.$

赛时思路

范围 3k，一眼 $O(n^2)$。想到了两个思路：DP 或转为无向图用 Tarjan 求割点。

• 一开始把 Tarjan 打出来并调好了，可是发现这样不对，因为就算整个图不连通起点和终点也可能连通。

• 再想了想 DP，憋了半天硬是想出来从起点和终点 DP 两次了，可是推了半天也不知道怎么用这个求 “堵点”。一开始想到转移 “某点是否可能成为堵点” 这个状态，发现根本行不通。

• 后来考虑爆搜 + 剪枝拉满。首先我们枚举堵点，

  • 这个点一定得在起点到终点的路径上吧，结合双向 DP，如果两次 DP 某个点都被遍历到了，说明确实在路径上。

  • 如果这个点四周都是空的，肯定不可能是堵点。

• 尝试把每个决定枚举的点堵上，然后跑一遍连通性。

DP 复杂度：$O(mn)$；搜索：$\le O(m^2n^2)$。总复杂度：$\le O(m^2n^2)$。居然 AC 了！！而且绰绰有余。

老师：还有这种操作。

正解

第一次 DP 的结果，即到起点的方案数记为 $f(x,y)$，第二次 DP 即到终点的方案数记为 $g(x,y)$，如果某个点满足 $f(x,y)\times g(x,y)=f(n,m)$，说明这个就是我们想要的堵点。

太妙了！！！！！

注意到 “方案数” 有这样的性质（其实是废话），记起点为 $s$，终点为 $t$。

• $s\to u$ 的方案数 = $u\to s$ 的方案数。

• $t\to u$ 的方案数 = $u\to t$ 的方案数。

那么堵点有什么性质呢？所有 $s\to t$ 的路径都要经过它，所以自然有 $f(x,y)\times g(x,y)=f(n,m)$，排列组合的乘法原理。

但是我们要枚举每个点 $u$，求 $u\to t$ 的长度，这样做复杂度太高了。反过来从 $t$ 开始 DP 就好了。

总复杂度：$O(mn)$。