思路
- 关键性质：对任意人位置 (x,y)，对角线上出口 (i,i) 的距离为 ∣x−i∣+∣y−i∣。当 i∈[min(x,y),max(x,y)] 时，有
∣x−i∣+∣y−i∣=∣x−y∣
且这是最小值。因此该人可选择的最近出口集合恰为整数区间
P3383.第2题-逃出迷宫
题目内容
给定一个大小为几 n×n 的迷宫，迷宫的单元格以坐标 (x,y) 表示，其中 1≦x,y≦n 。
在迷宫中有 m 个人，每个人初始位于坐标 (xi,yi) 。他们每一步可以移动到一个与当前位置四相邻的单元格。
在坐标 (i,i)(1≦i≦n) 的位置上有 n 个出口。每个出口只能使用一次，当有人在该出口逃出迷宫后，该出口即刻关闭。
每个人会选择离自己最近的出口(最小曼哈顿距离)作为逃生终点。若存在多个最近的出口，人员之间会协调分配，以使最终逃出的人数最大化。
当所有人按照上述规则前往各自目标出口后，计算最终有多少人能够成功逃出迷宫。
【名词解释】
-
四相邻：四相邻 是指当 ∣x−x′∣+∣y−y′∣=1 时，单元格 (x,y) 与 (x′,y′) 被认为相邻的，可以在一步中相互移动。
-
曼哈顿距离：两个点 (x1,y1),(x2,y2) 之间的曼哈顿距离为他们横坐标加纵坐标差，即 ∣x1−x2∣+∣y1−y2∣
输入描述
第一行输入两个整数 n 和 m(2≦n,m≦106) ，分别表示迷宫的边长与人的数量。
接下来 m 行，每行输入两个整数 xi 和 yi (1≦xi,yi≦n) ，表示第 i 个人的初始坐标。
输出描述
输出一个整数，表示最终能够逃出迷宫的人的数量。
样例1
输入
2 3
1 2
2 1
1 1
输出
2
说明
在这个样例中：
-
迷宫有 2 个出口，分别位于 (1,1) 和 (2,2)；
-
3 位人分别位于 (1,2),(2,1),(1,1) ；
-
每个出口只能使用一次，所以最多有 2 个出口被使用，因此共有 2 人逃出。
样例2
输入
4 3
1 2
1 2
1 2
输出
2
说明
在这个样例中：
-
迷宫有 4 个出口，分别位于 (1,1),(2,2),(3,3),(4,4) ；
-
3 位人分别位于 (1,2) ，距离出口的距离为 1,1,3,5
-
他们三人都只会选择 (1,1),(2,2) 的出口，因出口有人进入后会关闭所以三人中只有两个人能逃出。
-
出口 (3,3) 和 (4,4) 未被使用，因为它们并非任何人的最近出口(距离为 3,5 ) 。
