OpenJudge

04:迷阵

总时间限制:
1000ms
内存限制:
65536kB
描述

小Z每年都会为程设课出一道大作业,荼毒学弟学妹,可谓罪大恶极不可饶恕。

终于有一天,神明也看不下去了,他唤醒上古四大神兽,决定围困小Z,威慑一番。

于是,在小Z下一次醒来时,他便发现自己已然身处不知名的所在,抬眼所见,只有滚滚迷雾席卷而来,雾霭深处还隐隐约约闪着雷光。

低头一看,地上有一红漆木盒,上书四个大字“求生之道”,打开一看,竟是一台电脑。

电脑上空荡荡的,只有三个文件,一个是 Visual Studio 的安装包,一个是 README.txt,还有一个是 map.png。

小Z想都没想就开始安装 VS,在漫长的等待中,他打开了 README.txt:

“汝罪大恶极,故略施薄惩。此乃四象迷阵,有神兽镇守,踏错一步,险象环生。如欲得生,须观 map.png,寻得最短出路。”



迷阵是 m 行 n 列的格子矩阵,行、列从 1 开始数。小Z出生在左上角,也就是第 1 行,第 1 列的格子,迷阵的出口在第 m 行,第 n 列。

迷阵中有三种格子:

1. 空格子,以英文句点'.'记。出生点和出口都是空格子。
2. 墙,以井号'#'记。小Z无法移动到墙上。
3. 陷阱,以星号'*'记。小Z移动到陷阱的瞬间会受到来自上古神兽的 1 点伤害(生命 - 1),但是离开陷阱的瞬间不会再受到伤害。

小Z的生命有 H 点,当生命到 0 的瞬间他就会被传送回出生点。

小Z的每次行动是向上下左右的四个方向之一移动一格。不能移动出界,不能移动到墙上,但是可以移动到陷阱上。

小Z需要在短短3个小时内写出程序,算出自己最少要走多少步才能走到出口。

但凡迷阵,必有生门。题目保证必定存在一条路径使得小Z能够走到出口。

输入
第一行是一个整数 T,表示输入包含 T 组数据,分别是不同的平行时空下小Z所处的迷阵。

对于每组数据,第一行包括三个整数:m(2 <= m <= 255)、n(2 <= n <= 255)、H(1 <= H <= 5)。

接下来 m 行,每行是一个由符号组成的长度为 n 的字符串,第 i 行的第 j 个字符表示矩阵中第 i 行第 j 列的格子的类型。

题目保证出生点和出口(左上角和右下角)都是空格子。
输出
对于每组数据,你需要输出一行一个正整数,表示小Z在这个迷阵中最少要走多少步才能走到出口。

题目保证小Z一定能走到出口。
样例输入
2
2 2 3
.*
#.
5 5 3
.....
****.
.....
.****
.....
样例输出
2
8

01答案需要使用long long表示
05表达式期望值,Ai小于2^20

全局题号
15284
提交次数
1506
尝试人数
350
通过人数
187