OpenJudge

04:Maze

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

Maze is an m*n matrix, whose row and column number count from 1. You were born at the top left corner, that is the coordinate (1, 1), and the exit is at the coordinate (m, n).

There are three kinds of points in this maze:

  1. Empty point, denoted as ‘.’.  The birth point and the exit point are both empty points.

  2. Wall, denoted as ‘#’. You cannot move to the wall.

  3. Trap, denoted as ‘*’. When you move to the trap, your life will decrease by 1.

Your life value is H. When your life value decrease to 0, you will be transferred to the birth point. You can move to an adjacent point (Up, Down, Left or Right) at each step. You can move to the empty point and the trap, but you are not allowed to leave the matrix or move to the wall. You are required to calculate how many steps you need at least to reach the exit.


输入
The first line is an integer T, denoting the number of cases.
For each case, the first input line contains three integers: m (2<=m<=255), n (2<=n<=255), H (1<=H<=5).
For the following m lines, each line is a string with length of n. The jth character of ith lines denotes the type of the responding point.
输出
For each case, you are required to output an integer, denoting the steps you need at least to reach the exit. Note that the input can guarantee that you can reach the exit.
样例输入
2
2 2 3
.*
#.
5 5 3
.....
****.
.....
.****
.....
样例输出
2
8

01 Use "long long" to calculate the answer
05 Expected Value of an Expression: Ai is less than 2^20

全局题号
15298
提交次数
152
尝试人数
41
通过人数
32