No.402 最も海から遠い場所

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 109
作問者 : AreTrashAreTrash / テスター : TawaraTawara
7 ProblemId : 1152 / 出題時の順位表
問題文最終更新日: 2016-10-07 21:49:55

NOTE

作者の解法で、C++, C#, Java, PyPyについてはすべてのテストケースを通すことができることを確認していますが、それ以外の遅い言語で通すのは難しいかもしれません。

問題文

縦$H$、横$W$のサイズの地図があります。地図には、その場所が陸地か海かの情報が与えられます。地図外の領域はすべて海です。
海からのチェビシェフ距離が最も遠い場所のその距離を求めてください。

(追記)
1. 2点$(x_1, y_1), (x_2, y_2)$間のチェビシェフ距離は、$max(|x_1-x_2|, |y_1-y_2|)$で表されます。
2. ある陸と海との距離は、ある陸と全ての海であるマスとのチェビシェフ距離の内、最小の値です。

入力

$H$ $W$
$S_1$
$S_2$
$\vdots$
$S_H$

一行目に地図のサイズを示す$H$と$W$がスペース区切りで与えられます。
二行目以降の$H$行に地図を表す$W$文字の文字列が与えられます。
"#"は陸、"."は海を表します。陸は必ず一つ以上存在します。

$H$と$W$は整数、$1 \le H,W \le 3000$
$S_i$は"#"と"."からなる$W$文字の文字列

出力

海からのチェビシェフ距離が最も遠い場所のその距離を出力してください。

サンプル

サンプル1
入力
8 8
.#..#...
.######.
#####...
#####.#.
########
######.#
#####...
...####.
出力
3

緑色の部分を陸、水色の部分を海として、それぞれの陸地の海からのチェビシェフ距離は下図のようになります。
チェビシェフ距離が最も大きい場所のその値は3なので、それを出力します。

サンプル2
入力
7 7
#######
#######
#######
#######
#.#####
#..####
#######
出力
3

島の中に海が存在する場合があります。
また、地図の範囲外は全て海であることに注意してください。

サンプル3
入力
60 60
............................................................
............................................................
........................................#...............##..
.......................................####............##...
.........................................##...........##....
.........................................###........#.......
.........................................#####...#..#.......
.........................................#########....#.....
........................................###########.........
........................................#############.......
.....................................##.##########..........
......................................#########.............
.....................................#########..............
....................................##.#...###..............
...................................###.......#..............
.....................................###....................
.....................................#......................
.......................................##...................
......................................#.#...................
.....................................####...................
.....................................####...................
.....................................#####..................
.....................................######.................
.....................................######.................
.....................................######.................
.....................................#####..................
....................................#####...................
....................................#####...................
....................................######..................
...................................#####....................
................................#.######....................
.................................#######....................
............................#...########....................
............................#.##########....................
...........................############.....................
...........................############.....................
..........................#############.....................
.........................###############....................
....................###..##############.....................
...............#####################.##.....................
..............###################.#..#......................
.....#......###############.####..#.........................
..........########......###.................................
..........####....##.#.#####................................
......#.##...#.######..###..................................
.....##.####...######..##...................................
......######..####.#........................................
...#...######.###...........................................
......##.####..#............................................
.......#.###................................................
........####................................................
.......####.................................................
.......####.................................................
.......#.##.................................................
............................................................
..........#.................................................
........#.#.................................................
............................................................
............................................................
............................................................
出力
4
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。