思路

• 关键性质：对任意人位置 $(x,y)$，对角线上出口 $(i,i)$ 的距离为 $|x-i|+|y-i|$。当 $i\in[\min(x,y),\max(x,y)]$ 时，有

且这是最小值。因此该人可选择的最近出口集合恰为整数区间

题目内容

给定一个大小为几 $n×n$ 的迷宫，迷宫的单元格以坐标 $(x,y)$ 表示，其中 $1≦x,y≦n$ 。

在迷宫中有 $m$ 个人，每个人初始位于坐标 $(x_i,y_i)$ 。他们每一步可以移动到一个与当前位置四相邻的单元格。

在坐标 $(i,i)(1≦i≦n)$ 的位置上有 $n$ 个出口。每个出口只能使用一次，当有人在该出口逃出迷宫后，该出口即刻关闭。

每个人会选择离自己最近的出口(最小曼哈顿距离)作为逃生终点。若存在多个最近的出口，人员之间会协调分配，以使最终逃出的人数最大化。