【解题思路】

　　显然，这题的答案是这个网格图的最小割。根据最大流-最小割定理，我们可以用网络流算法来求其最小割，时间复杂度最小为O(V²√E)（听说增广路算法会被网格图卡得很惨）。

　　特殊的，这个网格图是一个平面图，于是可以根据平面图最小割-最短路定理，转化为其对偶图的最短路，时间复杂度最小为O(kE)或O(Vlog₂V)（民科算法spfa前途不可估量）。

【参考代码】

　　恩，听说这题我当初RE得生活不能自理，于是直接贴了orz::hzwer大神的代码。。以后再补上吧（假装会去写的样子）。

bzoj1001题解