Aide: Problème de concours graphique: peut-être un Dijkstra modifié ou un autre algorithme alternatif

J’essaie de faire cet exercice de concours sur les graphes:

XPTO est un aventurier intrépide (un peu trop téméraire pour son propre bien) qui se vante d’explorer tous les coins de l’univers, aussi inhospitalier soit-il. En fait, il ne visite pas les planètes où les gens peuvent facilement vivre, il préfère celles où seul un fou irait avec une très bonne raison (plusieurs millions de crédits par exemple). Son dernier exploit tente de survivre dans Proxima III. Le problème est que Proxima III souffre de tempêtes d’acides hautement corrosifs qui détruisent tout, y compris les combinaisons spatiales spécialement conçues pour résister à la corrosion.

Notre intrépide explorateur a été pris dans une zone rectangular au milieu d’une de ces tempêtes. Heureusement, il dispose d’un instrument capable de mesurer la concentration exacte d’acide sur chaque secteur et les dommages causés à sa combinaison spatiale. Maintenant, il lui suffit de savoir s’il peut échapper à la tempête. Problème

Le problème consiste à trouver une issue de secours permettant à XPTO de sortir de la tempête nocive. Vous obtenez l’énergie initiale de la combinaison spatiale, la taille de la zone rectangular et les dommages que la combinaison spatiale subira en se tenant debout dans chaque secteur.

Votre tâche consiste à trouver le secteur de sortie, le nombre de marches nécessaires pour l’atteindre et la quantité d’énergie que votre costume aura lorsqu’il quittera la zone rectangular. La voie d’évacuation choisie devrait être la plus sûre (c’est-à-dire celle où sa combinaison spatiale sera la moins endommagée). Notez que XPTO périra si l’énergie de son costume atteint zéro.

S’il existe plusieurs solutions possibles, choisissez celle qui utilise le moins d’étapes. S’il y a au moins deux secteurs avec le même nombre d’étapes (X1, Y1) et (X2, Y2), choisissez le premier si X1 <X2 ou si X1 = X2 et Y1 <Y2.

Contraintes 0 <E ≤ 30000 l'énergie de départ de la combinaison
0 ≤ W ≤ 500 la largeur du rectangle
0 ≤ H ≤ 500 hauteur du rectangle
0 <X <W la position X de départ
0 <Y <H la position Y de départ
0 ≤ D ≤ 10000 les dommages subis dans chaque secteur

Consortingbution

Le premier chiffre donné est le nombre de cas de test. Chaque cas consistera en une ligne avec les nombres entiers E, X et Y. La ligne suivante aura les nombres entiers W et H. Les lignes suivantes contiendront la masortingce contenant le dommage que la combinaison spatiale subira dans le secteur correspondant. Notez que, comme c’est souvent le cas pour les passionnés d’informatique, (1,1) correspond au coin supérieur gauche.

Sortie

S’il y a une solution, la sortie sera l’énergie restante, les coordonnées X et Y du secteur de sortie et le nombre d’étapes de l’itinéraire qui mènera Rodericus à la sécurité. Au cas où il n’y aurait pas de solution, la phrase Goodbye cruel world! sera écrit.

Exemple de saisie

3 40 3 3 7 8 12 11 12 11 3 12 12 12 11 11 12 2 1 13 11 11 12 2 13 2 14 10 11 13 3 2 1 12 10 11 13 13 11 12 13 12 12 11 13 11 13 12 13 12 12 11 11 11 11 13 13 10 10 13 11 12 8 3 4 7 6 4 3 3 2 2 3 2 2 5 2 2 2 3 3 2 1 2 2 3 2 2 4 3 3 2 2 4 1 3 1 4 3 2 3 1 2 2 3 3 0 3 4 10 3 4 7 6 3 3 1 2 2 1 0 2 2 2 4 2 2 5 2 2 1 3 0 2 2 2 2 1 3 3 4 2 3 4 4 3 1 1 3 1 2 2 4 2 2 1 

Exemple de sortie

 12 5 1 8 Goodbye cruel world! 5 1 4 2 

Fondamentalement, je pense que nous devons faire une Dijkstra modifiée, dans laquelle la distance entre les nœuds est l’énergie de la combinaison (et nous devons la soustraire au lieu de la résumer comme il est normal avec les distances) et les étapes sont les …. étapes effectuées sur le chemin. Le pos avec le binôme bester (Energy, num_Steps) est notre “sortie”.

Important: XPTO ne peut évidemment pas se déplacer en diagonale, nous devons donc supprimer ces cas.

J’ai beaucoup d’idées, mais j’ai un problème à les mettre en oeuvre …

Quelqu’un pourrait-il m’aider s’il vous plaît à y penser avec du code ou du moins des idées?

Est-ce que je me trompe totalement?

Puisqu’il s’agit d’un problème de concours, je vais juste donner un petit indice:

Dans cet exemple, ce sont les nœuds qui ont du poids, pas les bords. Une façon de convertir un tel graphe en type habituel consiste à remplacer chaque nœud par deux nœuds, un nœud entrant et un nœud out , ainsi qu’un bord dirigé de dedans vers out avec un poids égal à celui du nœud d’origine. Ensuite, pour chaque bord dirigé dans le graphique d’origine, placez un bord dirigé du noeud out d’un noeud in noeud entrant du suivant.

Votre idée semble bonne – allez-y.

En passant, lorsque vous travaillez sur ces problèmes, essayez de travailler vous-même à la mise en oeuvre. Il est rarement utile de simplement voir la mise en œuvre de quelqu’un d’autre. Demandez de l’aide sur l’algorithme si vous en avez besoin, mais implémentez-le vous-même.

Vous n’avez pas à traiter cela avec des conversions non conventionnelles, comme vous l’avez dit (soustraire au lieu d’append, etc.).

Le chemin le plus court d’un nœud à un autre est celui qui minimise les dommages subis par la poursuite en cours de route, que ce trajet vous tue ou non.

Il vous suffit de trouver le chemin le plus court entre START et EXIT, en faisant la sum des arêtes, comme à l’approche habituelle de Dijkstra, puis de vous demander si ce chemin le plus court est réalisable pour la puissance de combinaison donnée. Si ce n’est pas le cas, alors Goodbye cruel world! .

Si vous insistez pour élaguer la recherche une fois que vous savez que vous ne pouvez absolument pas atteindre EXIT, l’append après la mise en œuvre ci-dessus est sortingvial: vous élargissez votre horizon de recherche dans votre recherche dans Dijkstra, si vous passez même au prochain nœud le plus proche. pour élargir de vous tue, alors le rest de l’espace de recherche sera également, de sorte que vous pouvez simplement avorter et au Goodbye cruel world! .

Quant au graphique lui-même, conceptuellement, c’est ce que vous voulez. Les sumts du graphe dirigé sont constitués de tous les nœuds de la grid, plus un nœud artificiel EXIT.

  • Tous les nœuds de bord ont un bord dirigé vers EXIT; le poids de ces arêtes est 0
  • Tous les nœuds voisins (non diagonaux) ont des bords dirigés entre eux
    • Du nœud n1 à n2 , le poids de l’arête (c’est-à-dire le coût du déplacement de n1 à n2 ) est le dommage subi en restant au nœud n2 (appelons ce damageAt[n2] , que vous obtenez de la masortingce D en entrée) .

Donc, le montant total minimum de dégâts que l’on doit subir pour passer de START à EXIT est damageAt[START] + costOf(shortestPathBetween(START, EXIT)) .

En résumé, cette approche:

  • Nécessite uniquement une implémentation standard de Dijkstra
  • Nécessite seulement une très petite modification pour append l’élagage
  • Nécessite seulement une transformation très simple de la grid d’entrée au graphe dirigé