QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 1024 MB Total points: 100
[0]

# 6166. 世纪大逃亡

统计

给定一张 N×M 的四连通网格图。有 Q 个人,第 i 个人初始时位于 (Xi,Yi)。你需要给所有人规划一条走到边界(第一行/最后一行/第一列/最后一列)上的路径,且任意两条路径不在网格处相交。

你需要判断是否有解。如果有解,你还需要求出所有人的路径长度之和的最小值。

输入格式

每个测试点中包含多组测试数据。

输入的第一行包含三个整数 N,M,Q

接下来 Q 行,每行两个整数 X,Y,描述每个点的坐标。

输出格式

对于每组数据:

  • 如果不存在合法方案,输出 -1
  • 否则,输出一行一个整数,表示所有人的路径长度之和的最小值。

样例数据

样例输入

4 4 2
2 3
3 3
5 5 3
2 3
2 4
3 2
6 6 5
2 3
3 2
3 3
3 4
4 3

样例输出

2
3
-1

子任务

对于 70% 的数据,1N,M200

对于 100% 的数据,1N,M20001NM200000


  1. 赛时并未提供数据组数,“请选手自行评估”
  2. 赛时并未提供空间限制,“请选手自行评估” QOJ 上设置为 1 GB。