Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem H: 简单的迷宫问题

Problem H: 简单的迷宫问题

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 192  Solved: 16
[Submit][Status][Web Board]

Description

`刚上四年级的Titicia最近爱上了迷宫游戏,有一次玩得竟然连作业都忘记交了,于是她的老师对她说:你啊!Too naive!玩游戏也要按照基本法,要节制有度╮(╯▽╰)╭,现在我给你出一道关于迷宫的题目,你能帮我解决吗?

现在一个迷宫,你可以看作一张N*M的地图,在迷宫中有些地方能走,有些地方不能走,且在迷宫中会有很多怪物,当走到怪物的位置可以选择杀掉怪物或者不杀,杀掉怪物需要花1体力。你一开始在迷宫的一个随机能走的位置,已知如果当前迷宫中没有怪物,那么每移动一步需要的体力为1,如果当前迷宫中有N只怪物,那么每移动一步的体力为1+N,请问走到迷宫的出口最少需要多少体力?为了简化问题,我们可以假设迷宫中最多只有1只怪物。

Input

多组数据,请读入到文件结束。

每组数据首先输入N, M。(1<=N, M <= 50

然后输入N*M的矩阵表示迷宫的地图,其中“x”表示不能走,.”表示能走。

下一行输入SX, SY表示开始的坐标位置。

下一行输入EX,EY,表示迷宫的出口。

下一行输入一个数字K,表示迷宫中有几只怪物。

下面K行输入x,y表示怪物的坐标。

(坐标都从1开始)

Output

对每组样例,请先输出“Case #x:,x表示第几组数据。

然后换一行输出答案。若不能走到出口,输出-1

Sample Input

3 3
...
xx.
.x.
1 1
3 3
0

Sample Output

Case #1:
4

HINT

[Submit][Status][Web Board]