#P7367. [CTSC2002] 丹奇方块

[CTSC2002] 丹奇方块

题目背景

佳佳最近被一个叫做 “丹奇方块” 的游戏吸引住了,但是却因为游戏太难而迟迟无法通关。

题目描述

游戏在一个没有边界的棋盘上进行,中心 (0,0)(0,\,0) 处有一块黑色的障碍物,不远处坐标值为奇数的 NN 个不同的格子中各有一个灰色方块。

游戏的任务是把所有灰色方块全部粘起来组成一个给定的形状,如图一所示。该形状可以出现在棋盘上的任何位置,但不能旋转或者对称。图二描述了一个合法的初始状态,其中在坐标 (1,1),(1,1),(1,1)(-1,\,-1),\,(1,\,-1),\,(1,\,1) 处各有一个灰色方块。

这个游戏看起来简单,但方块数目多,目标形状又很复杂的时候游戏者往往需要很多步才能完成。佳佳希望找到一个不超过 20002000 步的解决方案,你能帮帮他吗?

输入格式

第一行包含一个整数 NN,即方块个数。

22 行包含 NN 个整数对 xi,yix_i,\,y_i 其中第 ii 个整数对代表第 ii 个方块的初始位置。位置按照从上到下(即 xx 递增)从左到右(即 yy 递增)的顺序排列。

33 行包含 NN 个 整数对 Pxi,PyiP_{x_i},\, P_{y_i},代表目标形状中各小方块的相对位置。目标方块保证是一个连在一起的整体,且数据总是有解的。

输出格式

一行,为需要的步数 SS

3
-1 -1 1 -1 1 1
7

提示

对于 100%100\% 的数据,3N203 \leq N \leq 209xi,yi9-9 \leq x_i,\,y_i \leq 91Pxi,PyiN1 \leq P_{x_i}, \, P_{y_i} \leq N