最短的时间

题目描述

师傅不幸被妖怪掳走，悟空决心即刻启程营救，但两地相隔甚远。此刻，他们手中握有一张详尽的地图，悟空位于坐标(sx,sy)，师傅被囚之地则标记为(ex,ey)。地图上的每个位置都标注了一个数字，这个数字代表着悟空经过该位置所需耗费的时间。悟空可以向上下左右四个方向自由移动。为了尽快救出师傅，悟空急需找到一条耗时最短的路径。

输入格式

第一行包含两个正整数 N 和 M 表示地图的长和宽（ 1 < N,M ≤ 20 ）

下面一行包含 4 个整数，前两个数表示猴哥的位置，后面两个数表示师傅位置；

接下来是一个N 行M列，每个数字表示当前位置需要用的时间（0<数字≤1000 ）

输出格式

一个整数，表示最短时间。

样例输入 #1

3 3
1 1 3 3
1 10 7
3 99 13
10 20 1

样例输出 #1

32

数据范围

1 < N,M ≤ 20，每个位置的耗时数字满足 0<数字≤1000。

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：Mid。

测试点分布