网格圈定边界转化为多源汇最短路问题：CF2109F

首先双方初始的答案是易求的。

考虑二分答案 $x$，考虑两种情况：

• $x\le dis_M$：相当于无限制

• $x > dis_M$

  这个情况我们可以推导出一个很关键的结论：我们可以钦定Mouf的最优路径

  钦定方法是显然的，在Mofu到终点的所有可行格子的范围内，我们选最靠近右上的一条路即可

现在问题转化为对于Fouad有一片范围，我们能不能弄出一个框架把它围住？

在本质上，围住的方法只有这六种：

我们重新考虑这个框架的形态，它其实是一条路径。这条路径相邻两个点之间可以通过边或者顶角相连。

我们把所有 $\ge x$ 的格子代价设为0，所有 $<x$ 的黑格子代价设为 $x-a$、白格子的代价设为 $-\inf$，那样子我们本质上其实就是跑一个多源汇最短路即可。