1952: 飞机迫降-泛洪算法

您正在玩一个游戏，给出一个地图，地图实际是一个 R 行 C 列的二维字符数组。'#' 表示障碍物,'.' 表示可通行格子，'v' 表示飞机。游戏中只有 1 架飞机，而且在第 1 行。

游戏有 3 个键：向左键、向右键、下降键。其中向左键可以把飞机向左移动一个格子，向右键可以把飞机向右移动一个格子，下降键可以把飞机向下移动一个格子。每按一次向左键需要消耗 1 个能量，每按一次向右键需要消耗 1 个能量，每按一次下降键需要消耗 0 个能量。

有一个特殊规定：对于地图的任意一行，飞机在该行所消耗的能量都不能超过 K。

你的任务是控制飞机降落，顺利到达第 R 行，不能碰到障碍物，而且消耗的总能量最少。

例如下图，R=7, C=9, K=2：

其中一种最优的方案是：

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

7 9 2
##..v..##
###.....#
#####...#
####...##
###..####
#.......#
#...#####

3