Pont – Regional event 2007

Level 4

ENONCE

Les hommes construisent trop de murs et pas assez de ponts. -- Isaac Newton

Le but de cet exercice est de construire un pont au dessus d'un fleuve. Évidemment, flemme oblige, on veut construire le pont là où le cours d'eau est le plus étroit. À partir d'une carte représentant le terrain, vous devez écrire une fonction qui renvoie la taille (en nombre de cases) du pont à construire.

La longueur du pont est le nombre de case que celui-ci prend sur la carte. Les différentes cases du pont doivent être adjacentes (gauche, droite, haut ou bas, mais pas de diagonale). Cela signifie que le pont n'est pas forcément "droit".

Le fleuve est représenté par le caractère . et la terre par le caractère #. On garantit que le coin en haut à droite et le coin en bas à gauche sont de la terre. Le fleuve sépare la terre en deux zones distinctes (comme dans l'exemple). Votre pont doit relier les deux continents.

CONTRAINTES

Les cartes pourront faire jusqu'à 50 par 50.

ENTREE

La première ligne de l'entrée contiendra 2 entiers la largeur X de la carte et sa hauteur Y

Les Y lignes suivantes contiennent X entiers correspondants à la carte.

SORTIE

Un unique entier : la longueur du plus petit pont pouvant relier les deux continents.

Runtime constraints

Maximum memory usage
70000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
28 17
.....#######################
........####################
...............#############
................############
#.............##############
##..#..........#############
######...........###########
######...........###########
#######...........##########
##########.........#########
############........########
#############........#######
#########..###.......#######
#########...........####..##
##########.......######...##
############........##.....#
#############...............
Sample output
5

Submit your solution

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