题目内容

在一张 $R$ 行 $C$ 列的网格地图上分布着 $K$ 个“危险源”，行列编号均从 $1$ 开始。一位移动者需要从起点 $(a_1, b_1)$ 前往终点 $(a_2, b_2)$。他每次可以向上、下、左、右四个方向之一移动一格，但不能走出地图边界。他希望规划一条路径，使得路径上经过的每一个位置都尽可能远离所有危险源。换句话说，他希望最大化整条路径上「各位置与最近危险源的曼哈顿距离」的最小值。

两个格子 $(x_1, y_1)$ 与 $(x_2, y_2)$ 的曼哈顿距离定义为 $|x_1 - x_2| + |y_1 - y_2|$。

若无论怎样移动都会经过某个危险源所在的格子（此时最近距离为 $0$），则答案视为 $0$。请你计算该最小值的最大可能值。

数据约束：

• 行数 $R$ 与列数 $C$ 均不超过 500，且格子总数 $R imes C \ge 3$。