Demi-finale 2007, épreuve machine - Pont
DIFFICULTE
LIMITE DE MEMOIRE
70000 ko
LIMITE DE TEMPS
1000 ms
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.
Les cartes pourront faire jusqu'à 50 par 50.
ENTREELa 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.
SORTIEUn unique entier : la longueur du plus petit pont pouvant relier les deux continents.
EXEMPLE(S) D'ENTREE/SORTIE
Exemple 1
en entrée ...
28 17 .....####################### ........#################### ...............############# ................############ #.............############## ##..#..........############# ######...........########### ######...........########### #######...........########## ##########.........######### ############........######## #############........####### #########..###.......####### #########...........####..## ##########.......######...## ############........##.....# #############............... |
5 |
Les partenaires grâce à qui Prologin peut exister :
