TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2004
  • 题目
  • P2004【CQOI2006】移动棋子
    限制 : 时间限制 : 50000 MS   空间限制 : 65536 KB
    问题描述

    在一个n*n的棋盘上有n枚棋子。每次可以把一枚棋子往上、下、左、右方向之一移动一格,最后排成一行、一列或者主、副对角线上(因此一共有2n+2条可能的目标状态),要求移动次数最小。
       棋盘上有一些位置是障碍,棋子在任何时候都不能经过。棋子的初始位置保证不在障碍物上。任两枚棋子不能在同时到达 同一个格子。

    输入格式

    第一行包含两个整数n, m,表示棋子的个数(它也是棋盘的边长)和障碍的个数。以下n行,每行两个整数(x, y),表示第i个棋子的坐标(1<=x, y<=n),以下m行,每行给出一个障碍物的坐标。假设这n+m个坐标两两不重合。

    输出格式

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

    样例输入

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

    样例输出

    6

    提示

    50%的数据满足:2<=n<=15,m=0
    100%的数据满足:2<=n<=50, 0<=m<=100