问题1214--贪吃蛇

1214: 贪吃蛇

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 512 MB

提交

题目描述

【问题描述】

蒟蒻doge最近沉迷于一款弱智游戏,贪吃蛇。

doge玩的贪吃蛇与普通贪吃蛇的规则略有不同。在一个n*m的迷宫里,有一条蛇想要走到出口,出口的坐标为(1,1)。这条蛇的身长为L,换句话说,它在任何时刻都会占L个格子。你每次让蛇头往上下左右中的一个方向前进一格,它的每节身体都会一次向前移动,即移动到前面一节身体原来所在的位置。

和普通贪吃蛇规则类似,蛇不能咬到自己,即如果某一时刻蛇的某两节身体在同一格子内,游戏就算失败。

与普通贪吃蛇不同的是,迷宫内没有食物,也就是说,蛇的身长不会改变。

迷宫内有一些障碍,蛇必须绕开障碍行走。

现在,蒟蒻doge想知道,想要让蛇头走到出口,最少要花多少步。

输入

【输入格式】

输入文件的第一行为一个整数T,表示数据组数,对于每组数据:

第一行有三个用空格隔开的数n,m,L,表示迷宫两边长和蛇的身长。

接下来L行描述蛇的初始状态,每行两个数。在这L行中,第i行的数表示蛇的第i节所在的坐标(蛇头为第1节)。

接下来一行一个整数k,表示障碍物数量。

接下来k行每行2个数x,y,表示坐标为(x,y)的点为障碍。

输入数据保证初始状态中:蛇不会咬到自己,蛇的相邻两节身体在地图中均相邻,蛇的每一节都在地图内。

输入数据保证障碍点均在地图内,并且没有重复的障碍点。

输出

【题意解释&样例解释】

所谓“蛇的移动”,请参考下图:(以样例为例,蛇头为1,依次标记)

                   初始状态                          蛇头向下移动1个单位后的状态

这条蛇到达出口的最佳方案是(4,1)(5,1)(5,2)(5,3)(4,3)(4,2)

(4,1)(3,1)(2,1)(1,1)(每时刻蛇头所在位置)

【数据范围】

测试点编号

n,m

L

T

测试点分值

1

n,m≤1000

L=1

5

25

2

n,m≤20

L4

5

25

3

L7

5

25

4

L8

5

25

对于所有数据,保证k+Ln*m

样例输入 Copy

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

样例输出 Copy

9
-1

来源/分类