Problem L: チクチクバンバン

Time Limit: 5 sec

屋根裏を整理していると，子供の時によく遊んだおもちゃが見つかった．このおもちゃはチクチクバンバンという名前で，サボテンを載せた貨物列車をレールから脱線しないように駅から駅まで運ぶというゲームだ．近所の子と一緒に熱中した懐かしい思い出が蘇り，掃除の途中であるのだが久しぶりに1回だけ遊ぶことにした．

このおもちゃの概観を図7に示す．

図7: チクチクバンバンの概観図．

このおもちゃは，1枚のフレーム， W×H−1 枚のタイル，1台の列車でできている．フレームには横幅 W，縦幅 H の長方形の窪みが空いていて，その窪みと隣接するように駅が2つ描かれている．タイルは 1×1 の大きさで上面にレールが彫ってあり，フレームの窪みにはめるとちょうど 1×1 の大きさの隙間が残るようになっている．この隙間と上下左右に隣接するタイルをスライドさせ，タイルと隙間の位置を入れ替えることによって，タイルの配置を変更することができるようになっている．

ゲームスタート時には，片方の駅に列車が置かれている（図7では列車を三角の印で表現している）．ゲームスタートと同時に列車は駅を出発し，レールに沿って移動し続ける．タイルの上のレールの形に関わらず，列車はあるタイルに入ってから出てくるまでにちょうど時間 1 を費やす．プレイヤーはタイルを適切なタイミングでスライドさせ，列車を脱線させないようにしなくてはいけない．脱線とは，レールが繋がっていない方向からタイルへ進入したり，タイルとタイルの隙間に落ちたり，駅以外のフレームに乗り上げたりすることである．列車がスタートした方とは異なる駅に到着することができたらゲームクリアである．

私はこのゲームをさんざんプレイしたことがあるため，タイルはいつでも好きな時に滑らかに，列車の速度に対して無視できる時間で動かすことができる．また，列車が乗っているタイルを列車ごとスライドさせるという高等テクニックも身につけている．そのため，慣れた手つきで格好良く軽々とクリアできるはずであった．ところが，長い間蒸し暑い屋根裏部屋に置いていたせいか，プラスチックが溶けてフレームとくっついてしまい，いくつかのタイルが動かなくなっていることがわかった．そのため，ゲームが非常に難しく，そしてより魅力的になってしまっていた．何度もプレイした結果，タイルの配置によってはクリアできるかどうかすら簡単にわからないこともあるということがわかった．

ここであなたにお願いがある．ゲームの初期盤面を与えると，その盤面がクリア可能かどうかを判定し，クリア可能なら列車の最短移動時間を求めるプログラムを書いて欲しい．もしプログラムが完成したなら，きっと私はこのゲームから足を洗うことができ，掃除の続きに戻ることができるだろうから．

Input

入力は複数のデータセットからなり， 1行目にデータセット数が与えられる．以降に，それぞれのデータセットが続く．

それぞれのデータセットは以下のようなフォーマットで与えられる．

W H
P₀ T₀ P₁ T₁
L₀
L₁
...
L_H−1

ただし，記号の意味は以下の通りである：

W, H はそれぞれ箱の横幅・縦幅を表し， 1 ≤ W, H ≤ 20 を満たす．
(P₀, T₀) と (P₁, T₁) はそれぞれ異なる2箇所の駅の位置を表す． P は 0, 1, 2, 3 のいずれかの値をもち，それぞれ駅がフレームの上辺・右辺・下辺・左辺に存在していることを意味する． T は P の値によってそれぞれ次のような意味を持つ：
- P = 0, 2 のとき，左からいくつの位置に駅があるかを表し， 0 ≤ T ≤ W−1 を満たす．
- P = 1, 3 のとき，上からいくつの位置に駅があるかを表し， 0 ≤ T ≤ H−1 を満たす．
L₀, ..., L_H−1 はそれぞれ長さ W の文字列であり，各文字は1つのタイルを意味し，全体で初期盤面の配置がどのようになっているかを表している．タイルにはそれぞれ図8のように名前がつけられており，動くタイルは名前が大文字で，動かないタイルは名前が小文字で与えられる．ここで，タイル D は，上下左右から列車が進入でき，進入してきた列車が直進してそのまま抜けていくタイルであり，また， E, F, G, H のタイルは，ある一方から来た列車が輪を描くように動き，同じ方向から出て行くというタイルである．初めの隙間の位置は “#” で与えられる．

図8: タイルの種類．

Output

データセットごとに，列車が駅間を移動するのに最低限必要となる時間を1行に1つ出力せよ．もし駅間の移動が不可能なら “-1” を出力せよ．

Sample Input

2
4 3
1 2 3 0
#bJG
KBBB
EeEA
6 5
3 4 1 2
aaaIMM
aaaIaA
N#BJDA
DaBaaa
MNBaaa

Output for the Sample Input

6
-1

サンプル入力の最初のデータセットの解決法を以下に示す．以下の説明において， t は列車がタイルに乗った瞬間からの時間を表す．図9において，列車は白い三角形の印で表し，固着したタイルはグレーで表している．

図9: サンプル入力の最初のデータセットの解決法．

左側にある駅からスタートする（図9 (a)）．
t = 0: タイルを上・左と移動させる（図9 (b)）．
t = 0 – 1.5: 列車を出発させ，時間が 1.5 経過する（図9 (c)）．
t = 1.5 – 2.5: タイルを右に移動し，時間が 1 経過する（図9 (d)）．
t = 2.5 – 3.5: タイルを左・左・下・左・上と移動し，時間が 1 経過する（図9 (e)）．
t = 3.5 – 4.5: タイルを右・右と移動し，時間が 1 経過する（図9 (f)）．
t = 4.5 – 5.5: タイルを左・左と移動し，時間が 1 経過する（図9 (g)）．
t = 5.5 – 6: タイルを右・上・左・下と移動し，時間が 0.5 経過する（図9 (h)）．

東京大学プログラミングコンテスト2008
Problemsetter: Yusuke Konishi