Problem
トレジャー ハンターのヴァシャは、古代のダンジョンの地図に出くわしました。ダンジョンはNMサイズの迷路(1NM100、NM100)。迷路の各セルは空で通過可能であるか、壁を含んでいます。セルから壁に隣接するセルにのみ移動できます (たとえば、各セルに隣接するセルは 4 つまでです)。
セルの 1 つに、Vasya が取得したい宝物があります。迷宮には、Vasya が旅を始めることができる K 個の入り口があります。
宝物までの距離が最短になるように、Vasya がどの入り口から旅を始める必要があるかを判断する必要があります。そのような入力が複数ある場合は、最も小さい番号の入力を出力してください。
入力
最初の行には、迷路の寸法を定義する 2 つの数値 N と M が含まれています。迷路の説明は次のとおりです。それぞれ M 文字の N 行。 0 は、セルが空いていることを意味します。 1.檻の中に壁があること。記号 * は宝物があるセルを表します (そのようなセルは迷宮内に 1 つだけあります)。
(N+2) 行目には数 K (1<=K<= NxM) -- 迷宮への入り口の数が含まれています。次に、K 行には入力の座標が含まれます。したがって、i 番目の行には数値 xi と yi が含まれます。これは、i 番目の入力が xi 番目の行の yi 列 (1xiN1yiM) にあることを意味します。入力の座標がペアごとに異なり、すべての入力が空のセルにあることが保証されます。宝箱の入り口はありません。
出力
必要な入力番号 (番号は 1 から始まります) を 1 つ表示する必要があります。宝物に到達できない場合は、-1 を出力してください。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
5 5
00000
00000
10*00
01111
00000
4
1 1
1 5
4 1
5 5
|
1 |
| 2 |
3 3
010
1*1
010
4
1 1
1 3
3 1
3 3
|
-1 |