Corruption – Qualification 2011

Énoncé¶

La licence d'utilisation de ProloGIMP a expiré. Joseph Marchand aimant autant l'argent que son chien, il refuse de la renouveler et décide plutôt de modifier des bits au hasard du fichier binaire de l'application. Grave erreur, il corrompt le pinceau !

On vous donne un tableau de bits représentant une image en noir et blanc, vous disposez d'un pinceau en forme de « + » (3 * 3 pixels). Chaque application du pinceau sur l'image (le centre du pinceau devant être dans l'image) inverse la couleur (les bits) des 5 pixels affectés. Vous devez implémenter une fonction déterminant s'il est possible de dessiner l'image donnée en entrée avec le pinceau, en partant d'une image dont tous les pixels sont blancs (à 0).

Dans le premier exemple, il est possible d'obtenir l'image en appliquant deux fois le pinceau: une première fois à la position (ligne, colonne) = (1, 1) et la deuxieme fois à la position (1, 2).

Contraintes¶

• 1 <= N <= 100 où N est la hauteur du tableau de bits.
• 1 <= M <= 15 où M est la largeur du tableau de bits.

Entrée¶

L'entrée standard contient N + 2 lignes :

• Le nombre N de lignes du tableau de bits.
• Le nombre M de colonnes du tableau de bits.
• Le tableau de bits (N x M) avec une espace entre les bits d'une ligne. 0 représente la couleur blanche, et 1 la couleur noire.

Sortie¶

Vous devez écrire une ligne sur la sortie standard :

• 1 si l'image est dessinable avec le pinceau, 0 sinon.