1383: 逃出生天

【问题描述】

     在冒险类游戏的某一关卡中，主人公需要穿越一个军工厂，才能获得最终胜利。根据军工厂的地图可以得到穿越提示，这份地图将军工厂划分成一个二维方阵，每个方阵在穿越是会消耗一定的体力值，为了保证在接下来的游戏中保存更多的体力值，你需要帮助主人公选择一条最佳路径，使其消耗的体力值最低。

     例如下面的二维方阵图1，每个位置都有一个数字，表示的是经过这个位置需要耗费的体力值。给定的起点和终点坐标后，主人公可以沿着八个方向（如图2）一步步的移向终点，请计算出从起点走到终点时，主人公所需的最低体力值。

二维方阵图1                       移动方向图2

     输入：第一行包含两个正整数N和M(1<N,M<30）表示地图的长和宽，下面一行包含4个整数，前两个数表示起点坐标位置，后面两个数表示终点坐标位置，最后是一个N行M列的二维数组，每个数字表示走当前位置需要消耗的体力值。（地图的左上角坐标为(1,1)）

     输出：一个整数，表示从起点走到终点时，主人公所需的最低体力值。

4 4
1 1 4 4
1 6 6 6
15 7 6 6
15 3 6 6
15 15 1 1

13