海岛问题

海岛问题"/>

海岛问题

      这是腾讯在编程马拉松比赛中的一道题，挺有趣的，留下来可以时不时地思考，或许可以找到更好的算法。

      开始步入正题吧：

      小Q漂流到了一座海岛上。这座海岛可以看作是一个矩形，划分为N*M个小格子，每个格子用(x,y)来表示，对应的海拔高度为h(x,y)。此外，海水会随着时间涨潮落潮，从海拔高度0涨到H，再落潮，高度回落至0，如此反复。当某个点的海拔高度小于潮水时，会从陆地变成海洋（不考虑该点是否被其他陆地包围），反之也会由海洋变为陆地。

 现在，小Q想要从海岛上的A地走到B地。走的时候只能从当前格子走到其相邻（上下左右）四个格子之一，且花费一定的体力x：

1.步行（从陆地到陆地）：x为两块陆地的高度差dH加上固定消耗F。

2.游泳（从海洋到海洋）：x为固定的S。

3.上岸或下水（从海洋或陆地到另一种地形）：x为陆地高出海水的差dH加上固定消耗 F。

小Q可以在原地等待潮水涨落到0到H之间的任意高度并随着潮水涨落，而无需消耗体力。为了简单起见，假定小Q每次移动可以在一瞬间完成，以至于在移动的过程中海水不会涨落。现在，给定一个起点和一个终点，不限小Q的移动时间，请求出小Q从A到B需要的最少体力。

输入：

输入包含多组数据，直到文件结束。对于每一组数据，第一行给出5个整数 N, M, H, S, F。N和M分别是海岛的长和宽，H是潮水的最大高度，S是小Q游泳到相邻点花费的体力。F 是步行、上岸、以及下水的固定消耗体力部分。

接下来一行是4个正整数sx,sy,tx,ty，（1<=sx,tx<=N，1<=sy,ty<=M）。(sx,sy)是小Q的起点，(tx,ty)是小Q的终点。接下来N行，每行M个数，用来描述每个点的海拔高度。

每一个输入的数字都是整数，其中2<=N,M<=100，2<=F,S<=100，0<=H, h(x,y)<=1000。

输出：

对于每组数据输出一行，输出小Q从起点到终点所需要的最小体力。