Coding Solution

Shadows of the Knight - Episode 1 – solution CodinGame en C

Moyenbinary search2D searchinteractive puzzleMis à jour le
Réponse courte

On maintient le rectangle des cases où la bombe peut encore se trouver, au départ tout l'immeuble. À chaque tour, la direction reçue le rétrécit (U ramène la borne basse à y - 1, D monte la borne haute à y + 1, l'absence de lettre verticale fixe y, et de même pour L et R sur x), puis on saute au centre du rectangle restant. Les deux axes sont divisés par deux en même temps, donc il faut environ log2(max(W, H)) sauts.

L'énoncé

Batman se trouve dans un immeuble de W x H fenêtres et doit trouver la fenêtre où la bombe est cachée avant d'épuiser un nombre limité de sauts. À chaque tour, le jeu indique la direction de la bombe par rapport à la fenêtre courante (U, UR, R, DR, D, DL, L ou UL) et on répond par les coordonnées de la prochaine fenêtre où sauter.

Les coordonnées commencent à (0, 0) dans le coin supérieur gauche, donc « haut » signifie un y plus petit. W et H peuvent atteindre 10 000, et le nombre de sauts autorisés est proche du minimum : il faut une stratégie qui écarte environ la moitié des cases restantes sur chaque axe à chaque tour.

La démarche, étape par étape

  1. Garder une boîte englobanteOn stocke xMin, xMax, yMin, yMax, initialisés à 0, W - 1, 0, H - 1. La bombe est toujours dans cette boîte, et la boîte ne fait que rétrécir.
  2. Mettre à jour les bornes verticalesSi la direction contient U, la bombe est au-dessus : yMax = y - 1. Si elle contient D, yMin = y + 1. Si elle ne contient ni l'un ni l'autre, la bombe est sur la ligne courante : yMin = yMax = y.
  3. Mettre à jour les bornes horizontalesMême logique sur x : L donne xMax = x - 1, R donne xMin = x + 1, et l'absence de lettre horizontale signifie xMin = xMax = x. Les deux axes sont traités indépendamment à partir du même indice.
  4. Sauter au centreOn se déplace en ((xMin + xMax) / 2, (yMin + yMax) / 2). Quel que soit l'indice suivant, au moins la moitié de l'intervalle restant est éliminée sur chaque axe non encore résolu.

Complexité

TempsO(log max(W, H)) turns, O(1) per turn
MémoireO(1)

Chaque axe est une recherche binaire distincte et les deux progressent en parallèle à chaque saut, donc le nombre de tours est celui de la plus grande dimension, pas la somme des deux.

Code de la solution

Shadows of the Knight - Episode 1 – C

#include <stdio.h>
#include <string.h>

int main(void) {
    int W, H, turns, x, y;
    scanf("%d %d %d %d %d", &W, &H, &turns, &x, &y);

    /* the bomb is somewhere in [xMin, xMax] x [yMin, yMax] */
    int xMin = 0, xMax = W - 1;
    int yMin = 0, yMax = H - 1;

    char dir[4]; /* up to 2 letters + '\0' */
    while (scanf("%3s", dir) == 1) {
        if (strchr(dir, 'U')) yMax = y - 1;
        else if (strchr(dir, 'D')) yMin = y + 1;
        else yMin = yMax = y;

        if (strchr(dir, 'L')) xMax = x - 1;
        else if (strchr(dir, 'R')) xMin = x + 1;
        else xMin = xMax = x;

        x = (xMin + xMax) / 2;
        y = (yMin + yMax) / 2;
        printf("%d %d\n", x, y);
        fflush(stdout);
    }
    return 0;
}

Erreurs fréquentes

Pour aller plus loin

La raison pour laquelle on tient dans la limite de sauts est qu'un seul indice porte de l'information sur les deux axes à la fois : « UR » est en réalité deux réponses indépendantes, « y plus petit » et « x plus grand ». Les traiter séparément transforme le problème en deux recherches binaires ordinaires qui avancent en parallèle, d'où un coût de ceil(log2(max(W, H))) tours au lieu de la somme des deux logarithmes. Notez aussi que l'indice est relatif à la fenêtre courante, pas à la précédente, donc sauter exactement au centre de la boîte est optimal pour cet épisode. L'Episode 2 retire la direction et ne dit plus que WARMER, COLDER ou SAME, ce qui oblige à chercher un axe à la fois et à choisir les cibles de saut par réflexion autour du milieu de l'intervalle, un problème bien plus difficile.

Questions fréquentes

Heat Detector est-il le même puzzle que Shadows of the Knight - Episode 1 ?

Oui. CodinGame a renommé Heat Detector en Shadows of the Knight - Episode 1 ; les règles, les entrées et les cas de test sont identiques.

Pourquoi mon Batman épuise-t-il ses sauts ?

Le plus souvent, un axe n'est pas verrouillé quand l'indice n'a pas de lettre pour lui, ou les bornes sont posées à x ou y au lieu de x - 1 / x + 1, si bien que la boîte ne rétrécit pas.

Faut-il arrondir le centre vers le haut ou vers le bas ?

Les deux marchent tant que la case courante est exclue lors de la mise à jour des bornes. La division entière (arrondi vers le bas) est la plus simple et retombe toujours dans la boîte.

Puzzles similaires

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