災害対応シミュレーション

PCK君はワールドロボットチャレンジの災害対応シミュレーション部門に参加しています。この部門のミッションは、建物の中に取り残された人達を救助することです。

建物の内部は$H$行$W$列のマスに区切られた平面で表され、各マスは壁、道、障害物のいずれかです。建物には$N$人が取り残されていて、$N$台の救助ロボットのそれぞれが一人ずつ救出します。全てのロボットは１つの基地局からいっせいに出発し、それぞれが救出する人のもとへ向かいます。各ロボットは、現在の位置から同じ行か列にある隣接するマスに進むことができます。ただし、建物の外や壁のマスに進むことはできません。道と障害物のマスには複数のロボットが同時に入れます。また、障害物のマスに侵入すると、そのロボットはダメージ1を受けます。

ミッション達成のためにPCK君が行う最初のタスクは、取り残された人達全員を救助できるような基地局の適切な設置場所を選定することです。ロボットが基地局から人のいる場所に達する経路があるときは、その中からロボットが受けるダメージを最小にするような経路を必ず選ぶことができます。この前提のもとで、各ロボットが受けるダメージのうち最大の値が最も小さくなるような基地局を探すことにしました。ただし、基地局は道を表すマスに設置しなければなりませんが、そのマスに人がいても設置できます。

建物内部の情報と人の位置が与えられたとき、基地局の場所を選定して、その候補をひとつ報告するプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$H$ $W$ $N$
$s_{1,1}s_{1,2}$...$s_{1,W}$
$s_{2,1}s_{2,2}$...$s_{2,W}$
:
$s_{H,1}s_{H,2}$...$s_{H,W}$
$r_1$ $c_1$
$r_2$ $c_2$
:
$r_N$ $c_N$

１行目に建物内部を表す平面の行の数$H$ ($2 \leq H \leq 300$)、列の数$W$ ($2 \leq W \leq 300$)、人の数$N$ ($ 1\leq N \leq 300$)が与えられる。続く$H$行に$i$行$j$列目のマスを表す文字$s_{i,j}$が与えられる。$s_{i,j}$が'.', '#','@'のとき、それぞれ道、壁、障害物を表す。続く$N$行に、各人がいる場所を表す整数の組$r_i$ ($1 \leq r_i \leq H$), $c_i$ ($1 \leq c_i \leq W$)が与えられる。$r_i$と$c_i$は$r_i$行$c_i$列目のマスに人がいることを表す。ただし、人がいるマスは道であり、一つのマスに二人以上いることはない。

 

出力

基地局の場所を表す整数の組を空白区切りで1行に出力する。複数の候補がある場合は、行番号が最小のものを出力する。そのようなものが複数ある場合は、その中で列番号が最小のものを出力する。ただし、候補が無い場合は「-1 -1」を出力する。

入出力例

入力例１

3 4 2
.@.#
#.@@
.@..
1 1
3 4

出力例１

1 3

入力例２

2 6 2
#.@@.#
######
1 2
1 5

出力例２

1 2

入力例３

3 3 2
...
###
...
1 1
3 3

出力例３

-1 -1

 

Note

Algorithm

 

---