- 总时间限制:
- 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:

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

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

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