There is no Spoon - Episode 1 – solution CodinGame en C
On stocke la grille ligne par ligne, puis pour chaque case contenant '0' on avance vers la droite sur sa ligne et vers le bas sur sa colonne jusqu'au prochain '0'. On affiche les coordonnées du nœud, celles du premier nœud trouvé à droite et celles du premier nœud trouvé en dessous, avec -1 -1 quand le balayage atteint le bord. Avec une grille d'au plus 30x30, ce parcours direct est largement assez rapide.
L'énoncé
On reçoit une petite grille (largeur et hauteur au plus 30) où '0' représente un nœud d'alimentation et '.' une case vide. Pour chaque nœud, il faut indiquer à quels nœuds il se relierait horizontalement et verticalement : le nœud le plus proche à sa droite sur la même ligne, et le nœud le plus proche en dessous dans la même colonne.
Chaque ligne de sortie contient six entiers : x y du nœud, puis x y de son voisin de droite, puis x y de son voisin du bas, -1 -1 remplaçant un voisin absent. Les coordonnées sont données colonne d'abord, ligne ensuite. Le puzzle s'appelait auparavant APU: Init Phase et sert d'échauffement au bien plus difficile There is no Spoon - Episode 2.
La démarche, étape par étape
- Lire la grille ligne par ligneOn garde chaque ligne sous forme de chaîne ou de tableau de caractères et on l'indexe grid[y][x]. Fixer cet ordre dès le départ évite le bug le plus fréquent de ce puzzle : inverser x et y quelque part entre la lecture et l'affichage.
- Parcourir les nœuds dans l'ordre de lectureOn boucle sur y puis sur x, et on n'agit que sur les cases égales à '0'. L'ordre de lecture (de haut en bas, de gauche à droite) est celui des exemples : il vaut mieux s'y tenir plutôt que de collecter les nœuds dans un ensemble ou un dictionnaire sans ordre défini.
- Balayer vers la droiteDe x+1 à width-1 sur la même ligne, on s'arrête au premier '0'. Les cases vides sont ignorées, donc le voisin peut se trouver plusieurs colonnes plus loin : ce n'est pas simplement la case adjacente.
- Balayer vers le basMême chose de y+1 à height-1 dans la même colonne. Si l'un des deux balayages atteint le bord sans trouver de nœud, on écrit -1 -1 pour ce voisin.
- Afficher une ligne par nœudOn assemble les trois paires de coordonnées sur une seule ligne. Construire la ligne en un seul appel d'affichage évite un espace parasite en fin de ligne ou un retour à la ligne manquant.
Complexité
O(W·H·(W+H))O(W·H)Chaque nœud peut balayer une ligne et une colonne entières, soit au plus 900 × 60 comparaisons de caractères. Un parcours à rebours qui mémorise le dernier nœud vu par ligne et par colonne ramènerait le tout à O(W·H), mais c'est inutile à cette taille.
Code de la solution
There is no Spoon - Episode 1 – C
#include <stdio.h>
int main()
{
int width, height;
scanf("%d %d", &width, &height);
char grid[30][32];
for (int y = 0; y < height; y++)
scanf("%31s", grid[y]);
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
if (grid[y][x] != '0')
continue;
// closest node to the right on the same row
int rx = -1, ry = -1;
for (int k = x + 1; k < width; k++)
if (grid[y][k] == '0') { rx = k; ry = y; break; }
// closest node below in the same column
int bx = -1, by = -1;
for (int k = y + 1; k < height; k++)
if (grid[k][x] == '0') { bx = x; by = k; break; }
printf("%d %d %d %d %d %d\n", x, y, rx, ry, bx, by);
}
}
return 0;
}
There is no Spoon - Episode 1 – Python
width = int(input())
height = int(input())
grid = [input() for _ in range(height)]
for y in range(height):
for x in range(width):
if grid[y][x] != '0':
continue
# closest node to the right on the same row
right = next((f"{k} {y}" for k in range(x + 1, width) if grid[y][k] == '0'), "-1 -1")
# closest node below in the same column
below = next((f"{x} {k}" for k in range(y + 1, height) if grid[k][x] == '0'), "-1 -1")
print(f"{x} {y} {right} {below}")
Erreurs fréquentes
- Ne regarder que la case adjacenteLe voisin est le prochain nœud sur la ligne ou la colonne, pas la case en x+1. Une grille comme '0.0' doit donner 2 0 comme voisin de droite de 0 0, et non -1 -1.
- Inverser x et yL'entrée se lit ligne par ligne, donc l'indexation naturelle est grid[y][x], mais la sortie attend x en premier. Mélanger les deux fonctionne sur les exemples carrés et symétriques, puis échoue au premier test rectangulaire.
- Tampons de ligne trop courts d'un octetUne ligne de 30 caractères a besoin de place pour le retour à la ligne et le zéro terminal. Avec fgets, il faut au moins 32 octets, sinon le retour à la ligne déborde sur la lecture suivante et la grille devient incohérente.
- Formater différemment le cas -1 -1Quand un voisin manque, on affiche quand même deux nombres. Afficher un seul -1, ou rien du tout, rend la longueur des lignes incohérente et le validateur rejette la sortie.
Pour aller plus loin
Si vous attaquez ensuite There is no Spoon - Episode 2, il est rentable de calculer ces voisins en un seul parcours à rebours : on parcourt les lignes de bas en haut et les colonnes de droite à gauche en mémorisant, pour chaque ligne, le dernier nœud vu et, pour chaque colonne, le dernier nœud vu. Quand on tombe sur un nœud, ces deux valeurs mémorisées sont exactement ses voisins de droite et du bas, et on les remplace alors par le nœud courant. Le travail passe en O(W·H) et on obtient directement la liste d'adjacence dont la recherche par backtracking de l'Episode 2 a besoin, sans aucun rebalayage.
Questions fréquentes
APU: Init Phase et There is no Spoon - Episode 1, est-ce le même puzzle ?
Oui. CodinGame l'a renommé ; les règles, l'entrée et la sortie n'ont pas changé, donc une solution pour l'un passe l'autre.
Faut-il une structure de graphe ou un BFS ?
Non. La grille est elle-même le graphe et chaque nœud a au plus un voisin à droite et un voisin en bas : deux balayages linéaires par nœud suffisent.
Qu'affiche un nœud sans voisin ?
Ses propres coordonnées suivies de -1 -1 pour le voisin de droite manquant et/ou -1 -1 pour le voisin du bas manquant, toujours six nombres par ligne.