Shadows of the Knight - Episode 1 – solution CodinGame en C
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
- 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.
- 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.
- 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.
- 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é
O(log max(W, H)) turns, O(1) per turnO(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
- Oublier de verrouiller un axeQuand l'indice est juste « L » ou « R », la bombe est sur la ligne courante. Si on ne pose pas yMin = yMax = y, on continue à gaspiller des sauts en cherchant verticalement et on épuise les tours.
- Ramener les bornes à y au lieu de y - 1Écrire yMax = y après un « U » garde la ligne courante, dont on sait déjà qu'elle est fausse. Sur des intervalles étroits, le centre reste alors sur la même case et la recherche tourne en boucle.
- Inverser haut et basy croît vers le bas dans ce puzzle. Traiter U comme « augmenter y » envoie Batman du mauvais côté dès le premier saut.
- Chercher un axe après l'autreTerminer la recherche horizontale avant d'entamer la verticale coûte log2(W) + log2(H) sauts, ce qui dépasse la limite sur les grands immeubles. Il faut rétrécir les deux axes à chaque tour.
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.