Dans la lutte contre les incendies, ce qui est critique c'est le temps d'intervention. Vous connaissez peut-être déjà la règle : "lorsqu'un feu se déclenche, au bout d'une minute, cela nécessite un verre d'eau, au bout de deux minutes, un seau d'eau, et après trois minutes il faut une tonne d'eau". On souhaite donc s'assurer qu'il y a une caserne de pompiers à proximité de chaque habitation - car malheureusement les incendies ne sont pas toujours détectés dans les deux premières minutes ! Étant données la carte d'une ville et la position de ses casernes de pompiers, on va donc chercher l'endroit qui est le plus éloigné d'une caserne.
La carte de cette ville moderne est très simple : il s'agit d'une grille, avec K rues verticales et K rues horizontales. Les casernes de pompiers se trouvent toujours au niveau de l'intersection de deux rues. Votre but est de trouver, parmi toutes les intersections de rues se trouvant sur la carte, celle qui est la plus loin d'une caserne de pompiers. Vous devez alors afficher la distance entre cette intersection et la caserne qui en est la plus proche. L'illustration montre la carte de la ville. Les ronds rouges montrent les positions des casernes, le rond bleu indique le point le plus loin d'une caserne. Le résultat pour cette entrée est 4, et le chemin bleu indique une des manières d'atteindre cette distance. |
De plus, dans 35% des tests, on a K <= 50.
Vous devez écrire un seul entier sur la sortie : la distance maximale d'une intersection à la caserne la plus proche.
entrée :
7 5 0 5 6 3 4 1 5 5 1 0
sortie :
4