Le casse-tête de Scooby-Naire – Regional event 2011

Level 7

É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

Runtime constraints

Maximum memory usage
10240 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
2
1 1
1 1
0 1
1 1
Sample output
1
Sample input
4
3 4 2 4
3 3 3 4
1 1 1 1
1 1 0 1
1 1 1 1
1 1 1 1
Sample output
0

Submit your solution

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