90. 你不是這個時間軸的人吧

0 Judge

Code: 0


題目敘述

Homura 的能力是讓時間停止。在戰鬥的時候會在時間停止時移動,因此旁人看起來像是 Homura 有瞬間移動的能力。已知時間停止的世界可以表示為一個$R \times C$的地圖,最左上角為$(1, 1)$,右下角為$(R, C)$,地圖上每個點有著一個時間係數,Homura 每次可以選擇往上、下、左、右移動一步,移動一步須耗費的魔力量為兩格間的|時間係數差|。給定 Homura 的起點和終點,請輸出她至少要花多少魔力才能從起點移動到終點?

輸入

第一行包含兩個正整數$R$, $C$($1 \leq R, C \leq 1000$),表示時間停止的世界大小為$R \times C$

第二行包含四個整數$r_1, c_1, r_2, c_2$,表示起點在$(r_1, c_1)$,終點在$(r_2, c_2)$

接下來有$R$行,每行包含$C$個整數,表示每一格的時間係數,$-10^9 \leq $ 時間係數 $\leq 10^9$。

輸出

請輸出Homura是少要花費多少魔力並換行

範例輸入

5 4
1 1 5 4
3 6 0 -4
7 9 -9 1
2 4 4 4
3999 1 100 293
-21 -71 22 1

範例輸出

200

測資限制

  • 保證 $20\%$ 的測資 $R \times C \leq 10$
  • 剩下的 $80\%$ 無特殊限制

Judge Setting

run-time limit: 2000 ms
memory limit: 256000000 byte
測資數量: 5