Le casse-tête de Scooby-Naire – Épreuve régionale 2011

Énoncé¶

Scooby-Naire a inventé un nouveau casse-tête artistique. Il prend une grille de N × N pixels, et note en face de chaque ligne et de chaque colonne un nombre compris entre 0 et N. Il noircit également certaines cases de cette grille. Résoudre le casse-tête consiste à dessiner un motif en noir et blanc, en noircissant les bonnes cases, de telle sorte que les nombres écrits par Scooby-Naire correspondent aux nombres de pixels blancs sur les lignes ou les colonnes correspondantes. Attention, une case noircie par Scooby-Naire ne peut être blanchie.

Dans l'exemple 1 ci-dessous, le casse-tête peut être résolu en laissant en blanc les cases en bas à gauche et en haut à droite.

Entrée¶

• Sur la première ligne, l'entier N correspondant à la taille de l'image.
• Sur la ligne suivante, le nombre de pixels devant être blancs pour chacune des lignes (de haut en bas) de l'image.
• Sur la ligne suivante, le nombre de pixels devant être blancs pour chacune des colonnes (de gauche à droite) de l'image.
• Sur les N lignes suivantes, les N lignes de la grille, où un 0 représente une case que Scooby-Naire a noircie, et 1 une case qui peut être noircie ou non par celui qui résout le casse-tête.

Sortie¶

1 s'il est possible de dessiner un motif satisfaisant les contraintes données par Scooby-Naire, 0 sinon.

Contraintes¶

• 1 <= N <= 50