#P17825. [Ontak2022]GOC
[Ontak2022]GOC
题目描述
平面上有 枚硬币,第 枚位于 。你控制一名携带特殊磁铁的角色,初始位于 。
角色每次可以向上、下、左、右移动一个单位。磁铁会立即吸走所有与角色当前位置具有相同横坐标或相同纵坐标的硬币。
求吸走全部硬币需要移动的最短总距离,不要求返回起点。
输入格式
第一行一个整数 。接下来 行,每行两个整数 。
输出格式
输出最短总距离。
数据范围
;。原题没有要求硬币坐标互不相同。
子任务
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | n≤200 | 8 |
| 2 | n≤5000 | 10 |
| 3 | 所有 xᵢ,yᵢ≥0 | 9 |
| 4 | 所有 xᵢ≥0 | 16 |
| 5 | 无额外限制 | 57 |
样例 1
输入:
11
2 2
1 8
8 2
7 -3
1 -1
-1 -2
-2 -1
-5 -1
-6 1
-2 2
-1 3
输出:
10