Lacs de Finlande – Regional event 2007

Level 4

ENONCE

On représente une carte par un tableau de caractères à deux dimensions. Chaque caractère peut être soit # (de la terre), soit . (de l'eau). Un lac est une zone d'eau bordée de terre. Deux cases d'eau adjacentes appartiennent donc au même lac (deux cases en diagonale ne sont pas adjacentes). On garantit par ailleurs que le bord de la carte sera systématiquement de la terre.

On considère que la profondeur en un point correspond à la distance minimale entre ce point et la côte (zone de terre) la plus proche. Cette distance se compte en nombre de cases (distance Manhattan). Par exemple, une case d'eau adjacente à une case de terre aura une profondeur de 1.

Vous devez écrire une programme qui doit renvoyer la profondeur maximale qui existe sur la carte.

CONTRAINTES

Les cartes pourront faire jusqu'à 100 par 100.

ENTREE

La première ligne de l'entrée contient deux entiers X et Y

Les Y lignes suivantes contiennent X caractères qui correspondent à la carte.

SORTIE

La sortie contiendra un entier : la profondeur maximal présente sur la carte.

Runtime constraints

Maximum memory usage
8192 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
26 18
##########################
####....##################
##.........###############
##..........##############
##..........##############
#..........######.....####
#........######......#####
##.....#########......####
###..##########......#####
################.....#####
#################...######
##########################
########....##############
#######......#############
########....######..######
#################....#####
###################..#####
##########################
Sample output
4

Submit your solution

You have to register or log in to be able to submit your solution.