Rolling Dice

時間制限 : 1 sec, メモリ制限 : 131072 KB
英語版はこちら

Problem G: Rolling Dice

とある北の国は、偉大なる将軍様が統治している。その国では最近、偉大なる将軍様の命によって大量に作られた優美なるサイコロが国民一人一人に下賜された。国民はこの美しいサイコロを歓喜の涙と共に受け取り、老いも若きもサイコロを使ったゲームに熱中している。

このゲームは、偉大なる将軍様の崇高な理念に基づいて各マスに数字の書かれた h * w マスのグリッドの上で行われる。プレイヤーはスタートのマスにサイコロを置き、これを転がしながらゴールのマスまで移動させる。一回サイコロを転がし終わる度に、駆逐すべき敵国の邪悪なる陰謀により、その時にいるマスの数字とサイコロの底面の数の積だけのペナルティが発生する。また、偉大なる将軍様の強いご希望により、美しいサイコロは1が上を、2が南を、3が東を向いた状態で置かれることが決定された。サイコロの向かい合う面の数の和は7であるので、最初に北を向いている数は5であることが分かる。言うまでもなく、美しいサイコロをグリッドの外へとはみ出させた愚か者は速やかに処分される。

与えられたグリッドとスタートのマスの位置とゴールのマスの位置に対して、最も少ないペナルティで美しいサイコロを動かすことができる国民がいたならば、偉大なる将軍様はお喜びになる。そうでない国民は炭鉱送りだ。国民が偉大なる将軍様のご期待に答えるプログラムを作成せよ。

Input

各データセットの最初の行には2つの整数 h, w が書かれていて、これらはグリッドの行数と列数を表す。

続く h 行にはそれぞれ w 個の数字があり、これらは各マスに書かれている数を表す。左上が北西に対応している。

続く2行にはスタートのマスの行番号と列番号、ゴールのマスの行番号と列番号がそれぞれ与えられる。各行・各列には 0 .. h-1, 0 .. w-1 の行番号・列番号が振られている。

h = w = 0のとき、入力は終了する。

Output

それぞれのデータセットに対して最小のペナルティを出力せよ。

Constraints

  • 1 ≤ h, w ≤ 10
  • 0 ≤ マスに書かれている数字 ≤ 9
  • スタートのマスとゴールのマスは異なる。

Sample Input

1 2
8 8
0 0
0 1
3 3
1 2 5
2 8 3
0 1 2
0 0
2 2
3 3
1 2 5
2 8 3
0 1 2
0 0
1 2
2 2
1 2
3 4
0 0
0 1
2 3
1 2 3
4 5 6
0 0
1 2
0 0

Output for the Sample Input

24
19
17
6
21

Source: University of Aizu Programming Contest , Aizu-Wakamatsu, Japan, 2010-05-29
Problem Setter:  Takashi Tayama