首先这个是比较经典的最大流：从源点向红点连 \(1\) 流量的边，网格中每条边流量为 \(1\)，蓝点向终点连流量为 \(1\) 的边，最大流就是答案。
最大流不好算，我们考虑最小割。最小割相当于给每个点染上红色或者蓝色，要使得两端点异色的边最少。
直接做还是不好做，我们考虑挖掘一点性质。考虑一个红色的极大连通块，如果其没有连接到两个相对的边界，那么其全部染成蓝色不会更劣。因为如果没有连接到相邻的边界，那么其和蓝色相邻的长度大于其和原始红色/蓝色相邻的长度，则调整后不会更劣。
假设所有连通块都同时连接上下界，则我们可以说明，对于一列，同时存在红色和蓝色也是不优的，具体可以参考上面那个证明调整来做。因此，直接可以写出一个简单的 DP：设 \(dp_{i,0/1}\) 表示第 \(i\) 列是红色/蓝色的最小答案，可以 \(O(n)\) 解决 H1。
对于 H2 也是简单的，注意到 dp 状态不是很多，可以线段树+矩阵优化转移，就可以做到 \(O(n\log n)\) 带个 \(32\) 倍常数了（