Corruption – Qualification 2011

Level 4

É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.

Runtime constraints

Maximum memory usage
5000 kilobytes
Maximum execution time
2000 milliseconds

Input/output samples

Sample input
3
3
0 1 1
1 0 0
0 1 1
Sample output
1
Sample input
5
5
0 0 0 0 0
0 0 0 0 0
1 0 0 0 0
0 1 0 0 0
0 0 0 0 0
Sample output
0
Sample input
10
3
0 1 0
1 1 1
0 0 0
1 1 1
0 0 0
1 0 1
1 0 1
0 1 0
0 0 0
0 0 0
Sample output
1

Submit your solution

You have to register or log in to be able to submit your solution.