先判掉 $(1,1),(n,m)$ 本来就不连通的情况。考虑只加一个障碍什么时候合法，显然这个障碍必须在所有合法路径的交也就是割点上。而由于只能向右向下走，就可以找到两条路径 $A,B$，其中 $A$ 能往下走就往下走，$B$ 能往右走就往右走，此时可以发现任意一条合法路径一定在 $A,B$ 中间夹的区域中。

上图标出了一种情况，其中 # 代表障碍物，A B 表示了两条路径。那么在只有一个障碍物时，该障碍物只能放在 $A,B$ 路径的交（A&B） 的位置上。现在考虑多加一个障碍物，显然当第一个障碍物挡在 A&B 的位置时第二个障碍物就可以任意放了；而剩下的情况一定是一个障碍物放在 $A$ 上，另一个放在 $B$ 上。那我们不妨枚举 $B$ 上方的障碍物的位置，共 $B$ 的路径长度个即 $O(n+m)$ 个。

假设第一个障碍物放在了 New # 上，此时又变成了只有一个障碍物的情况，而原来的 $B$ 已被阻断，我们考虑找新的 $B$ 记作 $B'$。在保证 New # 没放在 A&B 的格子的情况下（避免数重）$B'$ 一定存在。设 New # 放在 $(i,j)$ 上，$B'$ 一定要经过 $j$ 这一列，不妨设它在 $(k,j)$ 时第一次经过第 $j$ 列。从小到大枚举 $k$（满足 $k\ne i$）找到第一个能从 $(1,1)$ 走到 $(k-1,j)$、从 $(k,j)$ 走到 $(n,m)$ 的 $k$，那么就可以通过从 $(k-1,j)$ 出发向前走、$(k,j)$ 出发向后走还原出 $B'$。

图中加粗的 B&B' 就是找到的 $(k,j)$。得到 $B'$ 计算答案时，为避免与第一步将障碍物放在 A,B 交点时数重，第二个障碍物的合法位置为所有在 $A,B'$ 且不在 $B$ 的位置（A&B'）。这一步可以通过走一遍 $B'$ 计算。总复杂度 $O(n^2)$。