Il faut sauver Loïs

Le chemin le plus court, mais pas n'importe lequel

Clark Kent, alias Superman est dans les locaux du Daily Planet, qui occupent tout un étage. Chaque bureau communique avec tous les bureaux voisins. Il se trouve actuellement dans le bureau Nord-Ouest et doit aller sauver Loïs située dans le bureau Sud-Est. Il a deux contraintes. La plus forte est qu'il doit passer par le moins de bureaux possible, afin d'arriver le plus rapidement auprès de Loïs. Il y a de nombreux chemins de longueur minimum (en voici deux par exemple) :

Deux chemins de longueur minimum

Mais chaque bureau contient un certain nombre de cristaux de Kryptonite, déposés par Lex Luthor. La deuxième contrainte pour Superman est de croiser le moins de cristaux de Kryptonite en chemin.

Le nombre de cristaux dans chaque bureau est donné en entrée du problème.

Exemple

Si par exemple, le plan de l'étage (il est plus grand en réalité) était :

17 15 08 05 10
08 16 06 10 12
19 10 05 15 12
05 19 20 17 18
06 15 18 14 09

alors Superman aurait la possibilité de prendre ce chemin :

17 15 08  .  .
 .  . 06  .  .
 .  . 05 15 12
 .  .  .  . 18
 .  .  .  . 09

Il traverserait alors 9 bureaux, ce qui est le minimum qu'il puisse faire, et ne croiserait que 105 cristaux de Kryptonite, ce qui est le minimum en passant par 9 bureaux.

Pour valider le défi, vous devez indiquer par avance à Superman le nombre de cristaux de Kryptonite qu'il va croiser s'il navigue au mieux.

Ce problème est tiré de c0d1ng UP 2016

Type de retour

un nombre entier

Entrée du problème

Lien vers les données d'entrée

Formulaire de réponse

Vous devez être connecté pour pouvoir répondre aux défis

Tags : cup16 recursivité optimisation