Pince os – Qualification 2011

Énoncé¶

Aujourd'hui, Joseph Marchand se sent l'âme d'un artiste. Il va peindre sa meilleure nature morte : Scooby-Naire.

On vous donne un tableau de bits représentant une image en noir et blanc, ProloGIMP 0.4.2β ne dispose que d'un pinceau en forme de « + » (3 x 3 pixels). Chaque application du pinceau sur l'image (le centre du pinceau devant être dans l'image, sinon le logiciel plante !) noircit les 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.

Contraintes¶

• 1 <= N <= 1000 où N est la hauteur du tableau de bits.
• 1 <= M <= 1000 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.