救基友记3

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

  话说CZ由于不守基道,被妖怪抓走了,好基友WP在努力讨好高富帅RQ救出CZ的同时,CZ也意识到了自己的错误,然后努力的想逃出妖怪的闺房。 
   妖怪的闺房是一个n*m的矩阵,并且某些地方安装了带锁的门,钥匙藏在闺房另外的某些地方。刚开始WP被关在(sx,sy)的位置,离开闺房的门在(ex,ey)的位置。WP每分钟只能从一个坐标走到相邻四个坐标中的其中一个。妖怪每t分钟回闺房视察一次,若发现CZ不在原位置便把他再拎回去。经过若干次的尝试,CZ已画出整个闺房的地图。现在请你帮他计算能否再次成功逃亡。只要在妖怪下次视察之前走到出口就算离开闺房,如果妖怪回来的时候刚好走到出口或还未到出口都算逃亡失败。

Input

 每组测试数据的第一行有三个整数n,m,t(2<=n,m<=20,t>0)。接下来的nm列为闺房的地图,其中包括:
. 代表路
* 代表墙
@ 代表CZ的起始位置
^ 代表闺房的出口
A-J 代表带锁的门,对应的钥匙分别为a-j
a-j 代表钥匙,对应的门分别为A-J

每组测试数据之间有一个空行。

Output

 针对每组测试数据,如果可以成功逃亡,请输出最少需要多少分钟才能离开,如果不能则输出-1

Sample Input

4 5 17
@A.B.
a*.*.
*..*^
c..b*

4 5 16
@A.B.
a*.*.
*..*^
c..b*

Sample Output

16
-1

Hint

 

Source