Coding Solution

Power of Thor - Episode 1 – solution CodinGame en C

Facilegame loopcoordinatesgreedystate trackingMis à jour le
Réponse courte

On compare les coordonnées de Thor à celles de l'éclair : on ajoute N ou S si les Y diffèrent, puis E ou O (W) si les X diffèrent, on affiche la direction obtenue et on met à jour la position de Thor nous-mêmes, car le jeu ne la renvoie jamais. Avancer en diagonale tant que les deux axes diffèrent donne le chemin le plus court, donc on arrive toujours dans le nombre de tours autorisé.

L'énoncé

Thor se trouve sur une grille de 40 x 18 cases et doit rejoindre un éclair de puissance immobile. La première ligne donne X et Y de l'éclair, puis X et Y de départ de Thor. L'origine est le coin supérieur gauche : Y augmente vers le bas.

À chaque tour, le jeu envoie le nombre de déplacements restants, et on répond par l'une des huit directions N, NE, E, SE, S, SW, W ou NW. Thor perd s'il sort de la carte ou s'il épuise ses déplacements avant d'atteindre l'éclair.

La démarche, étape par étape

  1. Lire les positions une seule foisSeule la première ligne contient des coordonnées. On stocke la position de l'éclair et celle de Thor (ou simplement leur différence) dans des variables qu'on mettra à jour soi-même.
  2. Choisir la composante verticaleSi Thor est au-dessus de l'éclair (Y plus petit), on va au S ; s'il est en dessous, au N ; si les Y sont égaux, pas de composante verticale.
  3. Choisir la composante horizontaleMême logique sur X : E si l'éclair est à droite, W s'il est à gauche, rien s'ils sont alignés.
  4. Afficher puis mettre à jourOn concatène les deux parties, verticale d'abord, on affiche, puis on déplace d'une case les coordonnées mémorisées de Thor sur chaque axe utilisé. Sans cette mise à jour, Thor dépasse la cible car le code le croit toujours au départ.

Complexité

TempsO(1) par tour
MémoireO(1)

Chaque tour, c'est deux comparaisons et deux incréments. Le nombre total de tours vaut max(|dx|, |dy|), la distance de Tchebychev entre Thor et l'éclair.

Code de la solution

Power of Thor - Episode 1 – C

Conserve les quatre coordonnées et met à jour X et Y de Thor après chaque déplacement. Le nombre de tours restants n'est pas lu ; CodinGame ne l'exige pas, mais le lire avec scanf est une meilleure habitude.

#include <stdlib.h>
#include <stdio.h>

int main(int argc, char** argv) 
{
    // Coordinates of the light and Thor
    int lX, lY, tX, tY;
    scanf("%d%d%d%d", &lX, &lY, &tX, &tY);

    for (;;) {
        if (tY < lY) {
            printf("S");
            tY++;
        }
        else if (tY > lY) {
            printf("N");
            tY--;
        }

        if (tX < lX) {
            printf("E");
            tX++;
        }
        else if (tX > lX) {
            printf("W");
            tX--;
        }
        printf("\n");        
    }
    return EXIT_SUCCESS;
}
            

Erreurs fréquentes

Pour aller plus loin

Le nombre de déplacements nécessaires est la distance de Tchebychev max(|dx|, |dy|), et non la distance de Manhattan |dx| + |dy|, car un pas en diagonale réduit les deux écarts d'un coup. La règle gloutonne « diagonale tant que les deux axes diffèrent, puis tout droit » atteint exactement cette borne : chaque tour réduit de un le plus grand des deux écarts, c'est pourquoi Thor ne manque jamais d'énergie. La version Java montre une reformulation utile : au lieu de suivre deux positions, on suit le vecteur Thor → éclair et on le ramène à (0, 0). On retrouve cette idée dans Shadows of the Knight et dans beaucoup de puzzles de déplacement où seule la position relative compte.

Questions fréquentes

Pourquoi Thor sort-il de la carte avec ma solution ?

Le plus souvent, le code ne met pas à jour la position de Thor. Le jeu n'envoie que ses coordonnées de départ : c'est à vous de les modifier après chaque déplacement.

Dans quel sens est le Sud dans Power of Thor ?

Le Sud correspond à Y croissant. L'origine (0, 0) est le coin supérieur gauche de la carte, comme dans la plupart des repères écran.

Faut-il lire le nombre de tours restants ?

Il est envoyé à chaque tour mais inutile pour ce puzzle. Le lire reste une bonne pratique pour garder l'entrée synchronisée si vous ajoutez de la logique plus tard.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome