【解题思路】
显然，这题的答案是这个网格图的最小割。根据最大流-最小割定理，我们可以用网络流算法来求其最小割，时间复杂度最小为O(V2√E)（听说增广路算法会被网格图卡得很惨）。
特殊的，这个网格图是一个平面图，于是可以根据平面图最小割-最短路定理，转化为其对偶图的最短路，时间复杂度最小为O(kE)或O(Vlog2V)（民科算法spfa前途不可估量）。
【参考代码】
恩，听说这题我当初RE得生活不能自理，于是直接贴了orz::hzwer大神的代码。。以后再补上吧（假装会去写的样子）。
原文：http://www.cnblogs.com/spactim/p/6273212.html