No.402 The Place Farthest from the Sea
AreTrash
TawaraNOTE
It has been confirmed that the author's solution passes all test cases in C++, C#, Java, and PyPy, but it may be difficult to pass in other, slower languages.
Problem Statement
There is a map of height $H$ and width $W$. The map gives information on whether each location is land or sea. All areas outside the map are sea.
Find the Chebyshev distance from the sea of the place that is farthest from the sea in terms of this distance.
(Addendum)
1. The Chebyshev distance between two points $(x_1, y_1), (x_2, y_2)$ is expressed as $max(|x_1-x_2|, |y_1-y_2|)$.
2. The distance between a land cell and the sea is the minimum value among the Chebyshev distances between that land cell and all sea cells.
Input
$H$ $W$ $S_1$ $S_2$ $\vdots$ $S_H$
The first line contains $H$ and $W$, the size of the map, separated by a space.
Each of the following $H$ lines contains a string of $W$ characters representing the map.
"#" represents land and "." represents sea. There is always at least one land cell.
$H$ and $W$ are integers, $1 \le H,W \le 3000$
$S_i$ is a string of $W$ characters consisting of "#" and "."
Output
Output the Chebyshev distance from the sea of the place that is farthest from the sea in terms of this distance.
Sample
Sample 1
Input
8 8 .#..#... .######. #####... #####.#. ######## ######.# #####... ...####.
Output
3
With the green parts as land and the light blue parts as sea, the Chebyshev distance from the sea of each land cell is as shown in the figure below.
The value at the place with the largest Chebyshev distance is 3, so output it.
Sample 2
Input
7 7 ####### ####### ####### ####### #.##### #..#### #######
Output
3
There may be sea inside an island.
Also, note that everything outside the range of the map is sea.
Sample 3
Input
60 60 ............................................................ ............................................................ ........................................#...............##.. .......................................####............##... .........................................##...........##.... .........................................###........#....... .........................................#####...#..#....... .........................................#########....#..... ........................................###########......... ........................................#############....... .....................................##.##########.......... ......................................#########............. .....................................#########.............. ....................................##.#...###.............. ...................................###.......#.............. .....................................###.................... .....................................#...................... .......................................##................... ......................................#.#................... .....................................####................... .....................................####................... .....................................#####.................. .....................................######................. .....................................######................. .....................................######................. .....................................#####.................. ....................................#####................... ....................................#####................... ....................................######.................. ...................................#####.................... ................................#.######.................... .................................#######.................... ............................#...########.................... ............................#.##########.................... ...........................############..................... ...........................############..................... ..........................#############..................... .........................###############.................... ....................###..##############..................... ...............#####################.##..................... ..............###################.#..#...................... .....#......###############.####..#......................... ..........########......###................................. ..........####....##.#.#####................................ ......#.##...#.######..###.................................. .....##.####...######..##................................... ......######..####.#........................................ ...#...######.###........................................... ......##.####..#............................................ .......#.###................................................ ........####................................................ .......####................................................. .......####................................................. .......#.##................................................. ............................................................ ..........#................................................. ........#.#................................................. ............................................................ ............................................................ ............................................................
Output
4
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。