KND君は会津大学に在籍する学生プログラマである。彼はプログラマーであるとともに格闘家でもある。そんな彼は甘党であることで知られてるが、特に生クリームが大好物である。生クリームを食べればコンクリートの壁を数回壊すことができるようになるほどである。そのパワーに興味をもった彼の隣人は、生クリームたっぷりの新商品、「マトクリーム」を用いて実験をすることにした。
その実験は、まず迷路を用意しKND君をそこに閉じ込める。その迷路には鍵がかかった扉、扉を開けるための鍵、マトクリームがそれぞれ1つずつ別のマスに存在する。彼は落ちている鍵を拾い、扉の鍵を開けることで外に脱出することが可能である。鍵を持っていなくても扉があるマスに移動することは可能である。また、マトクリームを食べることで迷路の壁を N 回だけ壊すことができるようになる。ただし外壁を壊して迷路の外に出ることはできない。さて、彼は最小何回のマス移動で迷路を脱出できるだろうか。
サンプル2つの迷路と最短の脱出経路は次の図で示される。SはKND君の初期位置、Mはマトクリーム、Kは鍵、Dは扉を表す。
入力は複数のテストケースからなる。 ひとつのテストケースは以下の形式で与えられる。 入力の終了を2つのゼロを含む行で示す。
(迷路の入力) xs ys xm ym xk yk xd yd N
ここで、
入力は以下の条件を満たす。
各テストケースにつきKND君が迷路から脱出する最小のマス移動回数を一行に出力せよ。
3 3 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 2 2 1 5 5 0 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 4 4 0 1 2 0 0
4 15