God 的怒火(anger)
题目描述
有一个 n 行 m 列的座位网格,你位于 (s,t)。其中有 k 个不能落脚的位置,均不等于起点。
一次跳跃可以到达与当前位置同行或同列的任意其他位置,可以跨越禁止位置,但不能落在禁止位置上。
对每个可以到达的其他非禁止位置,求从 (s,t) 到它的最少跳跃次数,再将这些次数相加。不可达位置不计入答案。
输入格式
第一行五个整数 n,m,k,s,t。
接下来 k 行,每行两个整数 xi,yi,表示一个禁止落脚的位置。
输出格式
输出一个整数,表示最少跳跃次数之和。保证答案在有符号 64 位整数范围内。
样例 1 输入
3 4 3 3 1
1 1
2 3
3 4
样例 1 输出
14
样例说明
到 (2,1),(3,2),(3,3) 各需一步;到 (1,2),(1,3),(2,2),(2,4) 各需两步;到 (1,4) 需三步。总和为 3×1+4×2+1×3=14。
数据范围
全部数据满足 1≤n,m≤106,0≤k≤106,1≤xi,s≤n,1≤yi,t≤m,(xi,yi)=(s,t)。
| 测试点 |
附加限制 |
| 1—4 |
n,m≤1000 |
| 5、6 |
k≤1000 |
| 7—10 |
无 |