Puzzle – Épreuve régionale 2003

Énoncé¶

On vous donne en paramètres deux tableaux d'entiers à deux dimensions, contenant uniquement des 0 et des 1.

Le premier tableau, de dimensions $4 \times 4$, représente une pièce d'un puzzle. Les 1 représentent les cases faisant partie de la pièce, les 0 représentent les cases qui ne font pas partie de la pièce.

Le deuxième tableau, de dimensions $10 \times 10$, décrit le puzzle en cours de réalisation. Les 1 représentent les zones du puzzle où se trouve déjà une pièce, et les 0 représentent les zones vides.

Vous devez déterminer s'il est possible de placer la pièce dans le puzzle, c'est-à dire, s'il est possible de trouver une zone $4 \times 4$ du puzzle, sur laquelle on puisse superposer la pièce, de telle sorte qu'à tous les endroits où se trouve un 1 dans le tableau décrivant la pièce, on trouve un 0 dans le tableau décrivant le puzzle.

Une pièce doit être placée telle-quelle, sans rotation ni symétrie.

Votre fonction doit renvoyer 1 s'il est possible de placer la pièce, 0 sinon.

Entrée¶

Vous devez lire quatorze lignes sur l'entrée.

• Les quatre premières lignes décrivent la pièce à placer dans le puzzle. Chaque ligne contient quatre chiffres, parmi 0 et 1, sans espace.
• Les dix lignes suivantes décrivent l'état actuel du puzzle. Chaque ligne contient dix chiffres, parmi 0 et 1, sans espace.

Sortie¶

Vous devez écrire une ligne sur la sortie :

• Un entier, valant 1 ou 0, suivant s'il est possible ou non de placer la pièce dans le puzzle.