QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 1024 MB Total points: 100

# 6166. 世纪大逃亡

Statistics

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

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

输入格式

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

输入的第一行包含三个整数 $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\%$ 的数据,$1 \leq N,M \leq 200$。

对于 $100\%$ 的数据,$1 \leq N,M \leq 2\,000$,$1 \leq NM \leq 20\,0000$。


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