题目描述
您正在玩一个游戏，给出一个地图，地图实际是一个R 行C 列的二维字符数组。‘#’表示障碍物,‘.’表示可通行格子，‘v’表示飞机。游戏中只有1 架飞机，而且在第1 行。
游戏有3 个键：向左键、向右键、下降键。其中向左键可以把飞机向左移动一个格子，向右键可以把飞机向右移动一个格子，下降键可以把飞机向下移动一个格子。每按一次向左键需要消耗1 个能量，每按一次向右键需要消耗1 个能量，每按一次下降键需要消耗0 个能量。
有一个特殊规定：对于地图的任意一行，飞机在该行所消耗的能量都不能超过K。
你的任务是控制飞机降落，顺利到达第R 行，不能碰到障碍物，而且消耗的总能量最少。
例如下图，R=7, C=9, K=2：
```
##..v..##
###.....#
#####...#
####...##
###..####
#.......#
#...#####
```
其中一种最优的方案是：
1、在第一行按“向右键”、“下降键”
2、在第二行按“下降键”
3、在第三行按“下降键”
4、在第四行按“向左键”、“下降键”
5、在第五行按“向左键”、“下降键”
6、在第六行按“下降键”
7、顺利到达最后一行。
总共消耗3 个能量，已经是最优解了。
输入
第一行，3 个整数：R、C、K。 1 <= R <= 50， 3 <= C <= 50, 0 <= K <= 47。
接下来是R 行C 列的二维地图。
对于地图的每一行来说，开头都是连续的若干个障碍物格子，结尾也是连续的若干个障碍物格子，中间是连续的可通行格子（看题干描述的例子）。第一行比较特殊，因为有驾飞机，所以有一个可通行格子被‘v’替代了。
输出
一个整数，顺利完成任务所需要消耗的最少能量。如果不能完成任务，输出-1。
样例输入输出
输入#1
复制
7 9 2
##..v..##
###.....#
#####...#
####...##
###..####
#.......#
#...#####
输入#2
复制
4 5 0
#.v.#
##..#
###.#
#...#
提示