Ayant entendu parler de l’épidémie d’obésité aux États-Unis, Farmer John veut faire faire davantage d’exercice à ses vaches et organise un marathon bovin. Le parcours comprend deux fermes et un chemin de routes successives entre elles. Pour maximiser l’exercice, il cherche les deux fermes les plus éloignées de la carte, la distance étant la somme des longueurs des routes du chemin. Trouvez la distance de cette paire la plus éloignée.

Entrée

• Lignes à partir de 1 : même format que « Navigation Nightmare ».

Sortie

• Ligne 1 : un entier, distance entre les deux fermes les plus éloignées.

Exemples

Entrée 1

7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S

Sortie 1

52

Remarque

Entrée

Même disposition des fermes que dans le problème 1.

Explication — Sortie

Le plus long marathon va de la ferme 2 par les routes 4,1,6,3 à la ferme 5, sur $20+3+13+9+7=52$.

Auteur : Brian Dean, 2004