Problem1176--逃离迷宫

1176: 逃离迷宫

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 268  Solved: 114
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI正处在由 N × M 个房间组成的矩阵迷宫中。为了描述方便,我们把左上角的房间的坐标定为(0, 0),右下角房间的坐标定为(N-1, M-1)。每个房间可能是3种状态之一:开放的、关闭的、或者上锁的。

开放房间用'.'表示。PIPI可以从一个开放房间到达另一个相邻的(上下左右)开放房间。

关闭房间用'#'表示。PIPI永远不能进入一个关闭的房间。

上锁的房间用大写字母('A', 'B', 'C' ...)表示。PIPI在取得相应的钥匙前不能进入上锁的房间,而一旦取得钥匙就可以反复进入上锁的房间。每个房间的锁都是不同的,相应的钥匙在迷宫中的某一房间里,PIPI进入该房间就可以取得钥匙。

PIPI一开始处于一个开放房间,坐标(a, b)。迷宫的出口是一个开放或者上锁的房间,坐标(c, d)。假设PIPI每移动到一个相邻房间需要花费单位1的时间,那么PIPI到达出口最少需要花费多少时间?

Input

第一行包含7个整数: N , M , K , a , b , c , d . 其中N , M是矩阵的行列数;K 是上锁的房间数目,(a, b)是起始位置,(c, d)是出口位置。(1 ≤ N, M ≤ 100, 0 ≤ K ≤ 5, 0 ≤ a, c < N, 0 ≤ b, d < M)

以下 N 行每行包含 M 个字符,表示迷宫矩阵。

再以下 K 行每行两个整数 x, y,依次表示上锁房间A , B , C ....的钥匙所在房间坐标。(0 ≤ x < N, 0 ≤ y < M)

Output

输出到达出口的最短时间。如果小Hi永远到达不了出口,输出-1。

Sample Input

4 4 2 0 0 0 3
.A.B
.#..
.#..
.#..
3 0
3 3 

Sample Output

15

Source/Category