にひきのきつね と くらがりのめいろ (Two Foxes and the Dark Maze)

きつねの太郎と次郎はきつねの遊園地に遊びに来ています。

楽しそうなアトラクションがたくさんありますが、太郎は迷路のアトラクションに興味を持ったようです。次郎はあまり乗り気ではないようですが、太郎の熱意に負けていっしょに迷路に入ることにしました。

この遊園地の迷路はすこし特殊です。というのも、スタートとゴールがあって、スタート地点からゴール地点を目指して歩くというものではないからです。

2匹は迷路の異なる地点からスタートします。そしてどこでもよいのでふたたび出会うことが目的です。

迷路はとても暗いので、2匹は自分がどこにいるのかわかりません。周りをみても、非常に暗いので自分のすぐそばのこともわかりません。そんな迷路で2匹が出会うための道具として、Moffle社の便利なタブレット fPad が支給されています。

太郎の fPad には迷路の地図が入っていて見ることができますが、次郎の fPad には地図が入っていません。太郎の fPad から次郎の fPad にはデータを送信することができます。次郎は地図を見られませんが、太郎からの情報を受け取ることができます。

2匹の fPad にはもう1つ機能が備わっています。これを使うと自分の周囲の情報を少しだけ得ることができます。

次郎は暗いところがこわいので、できるだけはやく太郎と会いたいと思っています。2匹の間の距離がどのくらいあるのか計算することができるでしょうか。

それもできるだけはやく知りたいので、fPad の機能を使う回数はできるだけ少ないほうがよいです。

迷路の情報が与えられる。迷路は縦 H 横 W の長方形グリッドで表され、各マスは壁か通路のいずれかである。迷路の外側はすべて壁になっており通過することはできない。

迷路の通路は木構造をなしており、すべての通路の幅と壁の厚さは1である。より正確に言うと、ある大きさの長方形に含まれる格子点を頂点とし、距離が1であるような2点間に辺が存在するようなグラフにおける任意の全域木に対し、その頂点と辺を通路とし、そうでない部分を壁としたあとにまわりを外壁で囲ったものがこの場合の迷路である。

図 1

図 1 は迷路の例を示している。迷路の大きさには一周りぶんの外壁も含まれる、すなわちこの場合 H = 7, W = 7 となることに注意せよ。

この迷路のどこかに太郎と次郎がいるが、その2匹の場所はわからない。なお、2匹の場所は必ず迷路内の通路のマスであり、2匹のいるマスは異なることが保証されている。

次のプロシージャを実装せよ:

• 次のパラメータを持つプロシージャ taro(W, H, M):
  • W -- 迷路の横幅。3 ≦ W ≦ 1 000 を仮定してよい。
  • H -- 迷路の縦幅。3 ≦ H ≦ 1 000 を仮定してよい。W と H はともに 3 になることはない、すなわち少なくとも 2 つ以上通路のマスが存在することを仮定してよい。
  • M -- 迷路の情報を表す整数の2次元配列。0 ≦ i ＜ H, 0 ≦ j ＜ W に対して M[i][j] は、迷路の上から i+1 番目で左から j+1 番目の区画が壁であることを表す 1 か通路であることを表す 0 のいずれかである。
  このプロシージャ中で send(b) を繰り返し呼び出すことで次郎にデータを送信することが可能である。ただし b は 0 または 1 でなければならない。このプロシージャは jiro(W, H, S, X) よりも先に1度だけ呼び出され、戻り値を持たない。
• 次のパラメータを持つプロシージャ jiro(W, H, S, X):
  • W -- 迷路の横幅。この値は taro(W, H, M) が呼び出された際の W の値と一致している。
  • H -- 迷路の縦幅。この値は taro(W, H, M) が呼び出された際の H の値と一致している。
  • S -- 太郎から送られてきたデータの長さ(ビット数)。
  • X -- S 個の整数からなる1次元配列。0 ≦ i ＜ S に対して X[i] は taro(W, H, M) 中で send(b) が i+1 回目に呼び出された際の b の値に等しい。
  このプロシージャは taro(W, H, M) が呼び出された後に1度だけ呼び出される。このプロシージャは迷路における太郎と次郎の間の最短距離を計算して戻り値として返す必要がある。ただし辺を共有するマスどうしの距離を 1 とする。

taro(W, H, M) およびjiro(W, H, S, X) 中では query(dx, dy) を繰り返し呼び出すことができる。query(dx, dy) は taro(W, H, M) 中で呼び出された場合は太郎の現在位置、jiro(W, H, S, X) 中で呼び出された場合は次郎の現在位置から右に dx マス、下に dy マス移動したマスが壁であることを表す 1 か通路であることを表す 0 を返す。

query(dx, dy) 呼び出しにおいては -1 000 ≦ dx, dy ≦ 1 000 でなければならず、dx, dy によって指定されるマスが迷路の外側でも構わない。迷路の外側を指定した場合には壁を表す 1 が返される。

W = 5, H = 7,

の場合を考える。太郎の現在位置が (1, 1), 次郎の現在位置が (2, 5) であるとする。ただし迷路の上から y+1 番目で左から x+1 番目のマスを (x, y) と表す。taro 中で query を呼び出した際のパラメータと戻り値の例を次に示す。

また、taro 中で send が次のように呼び出されたとする。

このとき jiro 呼び出しにおいて S = 5 であり、

となる。

この場合 jiro は 7 を返さなければならない。