1168 - King and Night

時間制限 1 秒 / メモリ制限 64 MB / 得点 2 / Writer ei1821 / x 4 / 統計 /


TLE
1sec
MLE
64MB
得点
2

問題

あなたはチェスをプレイしています。
しかし、あなたは頭がよろしくないので、どうしても勝つことができません。
圧倒的屈辱に怒り狂ったあなたは唐突にスタンド能力に目覚めました。
その名も盤上の支配者 - ゲームマスター -
能力はいくつかあります。
一つ、盤の大きさを自由自在に変化させる
二つ、盤面の許す限り味方の駒の数を自由自在に変化させる
三つ、敵の駒をキングのみにする
四つ、自らがナイトとなりすべての駒の動きを止めて好きなマスから好きなだけ動く

あなたはこの能力を最大限利用し、勝利をもぎ取ろうとしています。
まず、盤の大きさを縦横8×8から$H$×$W$の$H$$W$マスに変更し、味方の駒を好きなように配置しました。
相手はキング一体なので、勝利は確実です。
調子に乗ったあなたは、キングを何手で下すことができるのか気になりました。
正確に言うと、$Q$回ほどナイトの位置を入れ替えて、各マスからキングまでそれぞれ何手でたどり着くかを調べたいです。
強者の愉悦を楽しみましょう。

▼チェスのナイトについて


入力

盤の縦と横のマス数$H$と$W$が与えられ、その後盤の情報が与えられる
盤の情報は文字列で与えられる、1文字が1マスの情報をもつ
文字が'$K$'のとき、そのマスに相手のキングがいることを表す
文字が'#'のとき、そのマスに味方の駒があることを表す
文字が'.'のとき、そのマスは空であることを表す
ナイトの初期位置の入力回数$Q$と$Q$行に渡ってマスの座標が空白区切りで与えられる

H W
Map0,0 ... Map0,w-1
...
Maph-1,0 ... Maph-1, w-1
Q
Y0 X0
Y1 X1
...
YQ-1 XQ-1

出力

各マスから最小何回の移動でキングを倒せるかを$Q$行出力せよ
もしキングを倒せない場合は-1を出力する
最後の改行を忘れずに

制約

  • 2 ≤ $H$, $W$ ≤ 2*103
  • 1 ≤ $Q$ ≤ 104
  • 0 ≤ $X$i < $W$
  • 0 ≤ $Y$i < $H$
  • 駒が置かれたマスがナイトの初期位置になることはない
  • 入力はすべて整数である
  • 1つのマスに味方の駒が複数あってはならない

入出力例

例1

入力

10 10
..........
..........
..........
..........
..........
..........
......K...
..........
..........
..........
3
0 0
1 3
6 5

出力

4
4
3

キングは座標(6, 6)にいる
(0, 0)のナイトは(1, 2),(3, 3),(4, 5)と遷移しキングを打ち取る
(1, 3)のナイトは(2, 5),(4, 6),(5, 8)と遷移しキングを打ち取る
(6, 5)のナイトは(5, 7),(7, 8)と遷移しキングを打ち取る

例2

入力

10 10
..........
..........
..........
..........
.....#.#..
..###.#.#.
..#..#K#..
.....##.#.
.....###..
.....##...
4
0 0
1 3
6 5
9 9

出力

6
4
-1
-1

味方の駒があるマスにはナイトは行くことが出来ないためたどり着けない場合もある

例3

入力

10 9
.........
.........
...#.#...
..#...#..
....K....
..#...#..
...#.#...
.........
.........
.........
4
0 8
4 3
4 5
9 8

出力

-1
-1
-1
-1

どこにナイトを設置してもキングは打ち倒すことができない
所詮あなたはあなたなのだ