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

Time Limit: 0 msec / Memory Limit: 256 MB

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

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

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

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

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

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

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

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

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

課題

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

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

図 1

図 1

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

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

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

  • 次のパラメータを持つプロシージャ taro(W, H, M):
    • W -- 迷路の横幅。3 ≦ W ≦ 1 000 を仮定してよい。
    • H -- 迷路の縦幅。3 ≦ H ≦ 1 000 を仮定してよい。WH はともに 3 になることはない、すなわち少なくとも 2 つ以上通路のマスが存在することを仮定してよい。
    • M -- 迷路の情報を表す整数の2次元配列。0 ≦ i < H, 0 ≦ j < W に対して M[i][j] は、迷路の上から i+1 番目で左から j+1 番目の区画が壁であることを表す 1 か通路であることを表す 0 のいずれかである。
    このプロシージャ中で send(b) を繰り返し呼び出すことで次郎にデータを送信することが可能である。ただし b0 または 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,

M =
1 1 1 1 1
1 0 1 0 1
1 0 1 0 1
1 0 0 0 1
1 1 1 0 1
1 0 0 0 1
1 1 1 1 1

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

パラメータ 戻り値
query(2, 0) 0
query(-4, 3) 1
query(3, -1) 1

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

send(1)
send(0)
send(0)
send(1)
send(1)

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

X =  1
0
0
1
1

となる。

この場合 jiro7 を返さなければならない。

小課題

小課題 1 (13 点)

  • taro(W, H, M) および jiro(W, H, S, X)query(dx, dy) を何度呼び出しても構わない。
  • 太郎が次郎に送るデータの大きさ(S)は 1 000 050 以下でなければならない。

小課題 2 (11 点)

  • taro(W, H, M) および jiro(W, H, S, X)query(dx, dy) を何度呼び出しても構わない。
  • 太郎が次郎に送るデータの大きさ(S)は 500 000 以下でなければならない。

小課題 3 (21 点)

  • taro(W, H, M) および jiro(W, H, S, X)query(dx, dy) を呼び出す回数は合計で 200 回以下でなければならない。
  • 太郎が次郎に送るデータの大きさ(S)は 500 000 以下でなければならない。

小課題 4 (21 点)

  • taro(W, H, M) および jiro(W, H, S, X)query(dx, dy) を呼び出す回数は合計で 120 回以下でなければならない。
  • 太郎が次郎に送るデータの大きさ(S)は 500 000 以下でなければならない。

小課題 5 (最大で 34 点)

  • taro(W, H, M) および jiro(W, H, S, X)query(dx, dy) を呼び出す回数は合計で 120 回以下でなければならない。
  • 太郎が次郎に送るデータの大きさ(S)は 500 000 以下でなければならない。
  • 重要: この小課題の得点は query(dx, dy) が呼び出された回数の合計によって決まる。

    この小課題のテストケース t において、あなたの提出したプログラムが query(dx, dy) を呼び出した回数を Pt とする。すべての Pt の最大値を P とおく。この小課題のあなたの得点は次の規則によって決定される。

    • P ≦ 80 のとき、あなたには満点である 34 点が与えられる。
    • 80 < P < 120 のとき、あなたの得点は ((120-P) / 40)2 * 33 +1 の小数点以下を切り捨てた値である。
    • P ≧ 120 または 1 つでも出力が間違っている場合は、あなたの得点は 0 点である。

実装の詳細

制限

  • CPU 時間制限: 1 秒
  • メモリ制限: 256 MB
    注意: スタックのサイズには決められた制限はない。スタックとして使用されたメモリは、メモリ総使用量に含まれる。

インターフェース (API)

  • 実装フォルダ: maze/ (プロトタイプ: maze.zip)
  • 競技者が実装するファイル: maze.cpp
  • 提出ファイルのインターフェース: maze.h
  • 採点プログラムのインターフェース: grader.h
  • 採点プログラムのサンプル: grader.cpp
  • 採点プログラムの入力のサンプル: grader.in.1, grader.in.2, ...
    注意:採点プログラムのサンプルは次の書式の入力を読み込む。
    • 1 行目: 整数 W, H, tY, tX, jY, jX が空白区切りで書かれている。tY, tX は太郎の初期位置の座標を、jY, jX は次郎の初期位置の座標を表す。
    • 2 行目から H+1 行目: 0 ≦ i < H に対し、i+2 行目には W 文字の文字列 M[i] が空白区切りで書かれている。0 ≦ j < W に対し、M[i][j] は迷路の上から i+1 番目、左から j+1 番目のマスが壁であることを表す '#' か通路であることを表す '.' のいずれかである。
  • 採点プログラムの入力のサンプルに対して期待される出力: grader.expect.1, grader.expect.2, ...
    注意:採点プログラムのサンプルは次の書式の出力を書き出す。
    • 1 行目: プロシージャ jiro が返すべき値が書かれている。
  • 採点プログラムのサンプルは標準エラー出力に次の書式で情報を書き出す。
    • 1 行目: "S = S" が出力される。ただし S はこの実行で send が呼び出された回数である。
    • 2 行目: "#query = P" が出力される。ただし P はこの実行で query が呼び出された回数である。