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