#P5796. [CQOI2006] 移动棋子

[CQOI2006] 移动棋子

题目描述

在一个 n×nn\times n 的棋盘上有 nn 枚棋子。每次可以把一枚棋子往上、下、左、右方向之一移动一格,最后排成一行、一列或者主、副对角线上(因此一共有 2n+22n+2 条可能的目标状态),要求移动次数最小。

棋盘上有一些位置是障碍,棋子在任何时候都不能经过。棋子的初始位置保证不在障碍物上。任两枚棋子不能在同时到达同一个格子。

输入格式

第一行包含两个整数 nnmm,表示棋子的个数(它也是棋盘的边长)和障碍的个数。

以下 nn 行,每行两个整数 xxyy,表示第 ii 个棋子的坐标。(1x,yn1\le x,y\le n

以下 mm 行,每行给出一个障碍物的坐标。保证这 n+mn+m 个坐标两两不重合。

输出格式

输出仅包含一个整数,表示最小移动步数。如果无解,输出-1

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

提示

【样例解释】

【数据范围】

对于 50%50\% 的数据,n15n\le 15m=0m=0

对于 100%100\% 的数据,2n502\le n\le 500m1000\le m\le 100