BZPRO

#1326. Zju1361Holedox Moving

内存限制：162 MiB 时间限制：1 Sec
提交 提交记录 讨论

题目描述

有一条蛇在它的洞里面，现在他要出来，问最少要多少步才可以移动到出口。出口的位置是(1,1)。蛇可以弯曲的，但是它的部分必须是连接的，比如：如果它有一个部位在一个坐标，连接它那个部位的坐标一定是它的上下左右。

输入格式

有多组数据。每组数据的第一行有3个数，N,M,L（N，M）表示洞的大小N*M，L表示蛇的长度。然后下面有L行，每行两个数，表示蛇所有部位的位置。第一组是蛇的头，第L组是蛇的尾巴，也就是说是按顺序给出蛇的头至尾的位置，移动时蛇的蛇的后面一个部位要移到之前那个部位的位置。当然蛇不能走到有石头的地方且它不能走在自己身上。 然后给出一个K，表示洞里面有多少块石头。然后下面有K行，每行2个数，表示每块石头的坐标。 每个数据之间有一空行，数据以3个0表示结束。

输出格式

如果蛇可以走出洞的话，那么输出最小步数，如果蛇不能走出洞，那么输出-1；

样例

样例输入


			
5 6 4

4 1

4 2

3 2

3 1

3

2 3

3 3

3 4



4 4 4

2 3

1 3

1 4

2 4

4

2 1

2 2

3 4

4 2



0 0 0

样例输出


			
Case 1: 9

Case 2: -1

数据范围与提示

注意：出口处是没有石头的。

说明：第一组数据依次按以下坐标走是最短的。

(4,1) '(5,1) (5,2) '(5,3) '(4,3) '(4,2) '(4,1)' (3,1) '(2,1)'(1,1)

BZPRO Powered by Remmina.
Github Repository