Entraînement » Demi-finale 2003, épreuve machine » Casse-tête binaire

Demi-finale 2003, épreuve machine - Casse-tête binaire

DIFFICULTE

LIMITE DE MEMOIRE

10000 ko

LIMITE DE TEMPS

5000 ms

ENONCE

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*4 entiers, valant 0 (pour noir) ou 1 (pour blanc), et indiquant quelles cases contiennent des pions du côté noir, et quelles casent 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 ette 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 retourner le nombre minimum de coups nécessaires pour que tous les pions de la grille soient du côté blanc.

CONTRAINTES

ENTREE

Vous devez lire quatre lignes sur l'entrée, chacune contenant quatre chiffre (0 ou 1) sans espaces. Ces quatre lignes représentent les 4 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.

COMMENTAIRES

Pour l'exemple ci-dessous, Une succession de coups possible est, si l'on numérote les colonnes de 1 à 3, et les lignes de 1 à 3 :

  • rotation vers le haut de la colonne 2 :
1101
0010
1101
1101
  • retournement de la ligne 2 :
1101
1101
1101
1101
  • retournement de la colonne 3 :
1111
1111
1111
1111
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 : NOT binaire de a (inverse tous les bits). a ^ b : OU exclusif binaire entre a et b.

EXEMPLE(S) D'ENTREE/SORTIE

Exemple 1
en entrée ...

1101
0110
1001
1101
en sortie ...
3