Wall Breaker KND

Time Limit : 1 sec, Memory Limit : 262144 KB

Wall Breaker KND

Problem

KND君は会津大学に在籍する学生プログラマである。彼はプログラマーであるとともに格闘家でもある。そんな彼は甘党であることで知られてるが、特に生クリームが大好物である。生クリームを食べればコンクリートの壁を数回壊すことができるようになるほどである。そのパワーに興味をもった彼の隣人は、生クリームたっぷりの新商品、「マトクリーム」を用いて実験をすることにした。

その実験は、まず迷路を用意しKND君をそこに閉じ込める。その迷路には鍵がかかった扉、扉を開けるための鍵、マトクリームがそれぞれ1つずつ別のマスに存在する。彼は落ちている鍵を拾い、扉の鍵を開けることで外に脱出することが可能である。鍵を持っていなくても扉があるマスに移動することは可能である。また、マトクリームを食べることで迷路の壁を N 回だけ壊すことができるようになる。ただし外壁を壊して迷路の外に出ることはできない。さて、彼は最小何回のマス移動で迷路を脱出できるだろうか。

サンプル2つの迷路と最短の脱出経路は次の図で示される。SはKND君の初期位置、Mはマトクリーム、Kは鍵、Dは扉を表す。

Input

入力は複数のテストケースからなる。 ひとつのテストケースは以下の形式で与えられる。 入力の終了を2つのゼロを含む行で示す。

(迷路の入力)
xs ys
xm ym
xk yk
xd yd
N

ここで、

  • 迷路の入力:
    まず迷路の幅と高さを表す2つの整数 W , H が来る。次に 2 * H - 1 行の入力がある。このうちの奇数行目は横に隣合うマスの間の壁の有無を表す。最初に空白が1つあり、 W - 1 個の1か0が来る。1は壁があること、0は壁がないことを表す。偶数行目は縦に隣合うマスの間の壁の有無を表す。こちらは W 個の1か0が来る。同様に1は壁があること、0は壁がないことを表す。
  • xs ys:主人公の初期位置のマスの座標
  • xm ym:マトクリームのマスの座標
  • xk yk:鍵のマスの座標
  • xd yd:扉のマスの座標
  • N:マトクリームをとった場合に迷路の壁を壊せる回数

Constraints

入力は以下の条件を満たす。

  • 入力はすべて整数。
  • 2 ≤ W, H ≤ 20
  • 0 ≤ xs, xm, xk, xd < W
  • 0 ≤ ys, ym, yk, yd < H
  • 0 ≤ N ≤ 100
  • 主人公の初期位置のマスの座標、マトクリームのマスの座標、鍵のマスの座標、扉のマスの座標は互いに別の座標である。
  • 扉に入ることが不可能なデータセットはない。

Output

各テストケースにつきKND君が迷路から脱出する最小のマス移動回数を一行に出力せよ。

Sample Input

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

Sample Output

4
15

Source: Aizu Competitive Programming Camp 2012 , Day 3, Aizu-Wakamatsu, Japan, 2012-09-05
Problem Setter:  Kazuki Omomo, Yohei Mori, Yuya Watanabe