Prologin
2024
Énoncé¶
On vous propose un casse-tête, consistant en une grille de 4 cases sur 4, sur lesquelles sont placés des pions. Chacun de ces pions est noir d'un côté, et blanc de l'autre.
On vous fournit la position de départ, sous la forme d'un tableau de $4 \times 4$ entiers, valant 0 (pour noir) ou 1 (pour blanc), et indiquant quelles cases contiennent des pions du côté noir, et quelles cases contiennent des pions du côté blanc.
Le but du casse-tête est d'obtenir le plus rapidement possible une grille dont tous les pions sont du côté blanc, sachant que les opérations autorisées sont les suivantes :
- Retourner les 4 pions d'une ligne : les pions de cette ligne qui sont côté blanc deviennent noirs, et vice-versa.
- Retourner les 4 pions d'une colonne.
- Faire une rotation vers la gauche des pions d'une ligne : tous les pions sont décalés d'une case vers la gauche, sauf le pion le plus à gauche, qu'on place tout à droite. Aucun pion n'est retourné.
- Faire une rotation vers le haut des pions d'une colonne (même principe).
- Retourner 1 pion. Un pion blanc devient donc noir, et un pion noir devient blanc.
Chaque utilisation de l'une de ces opérations compte pour un coup, vous devez renvoyer le nombre minimum de coups nécessaires pour que tous les pions de la grille soient du côté blanc.
Pour les programmeurs C, nous vous rappelons les principaux opérateurs binaires disponibles :
a << b: décalage à gauche de b bits, du nombre a.a >> b: décalage à droite de b bits, du nombre a.a & b: ET binaire entre a et b.a | b: OU binaire entre a et b.~a: NON binaire de a (inverse tous les bits).a ^ b: OU exclusif binaire entre a et b.
Entrée¶
Vous devez lire quatre lignes sur l'entrée, chacune contenant quatre chiffres (0 ou 1) sans espace. Ces quatre lignes représentent les lignes de la grille.
Sortie¶
Vous devez écrire une ligne sur la sortie :
- Le nombre minimum d'opérations nécessaires pour obtenir une grille entièrement blanche.