Problem B: 中等迷宫问题

Problem B: 中等迷宫问题

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

Description

PIPI被困在一个n*m网格图组成的迷宫中,初始位置在S,出口在T。迷宫中的'.'代表该位置可以走,'#'代表该位置为障碍物,不能走。
PIPI除了能上下左右移动外,还支持遁地操作,使用一次遁地操作能够从(x,y)位置到达(n-1-x, m-1-y)位置,遁地操作一共能够使用k次。
请问PIPI从S到T所需的最短时间是多少。

Input

单组测试样例。
第一行输入迷宫大小n, m,以及PIPI一共能够进行的遁地次数 k 。(2n,m≤500, 0k≤10
接着输入一个n行m列的字符矩阵。

Output

如果PIPI能够从S到达T,输出所需的最短时间,否则输出-1。

Sample Input

4 4 2
#S..
T#..
....
....

Sample Output

4

HINT

首先从(0,1)遁地到(3,2),再往上一步到达(2,2),再往右一步到达(2,3),最后遁地到达(1,0),共4步。