No.402 最も海から遠い場所
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 160
作問者 :
AreTrash
/ テスター :
Tawara
タグ : / 解いたユーザー数 160
作問者 :
AreTrash
/ テスター :
Tawara
問題文最終更新日: 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
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。