Puzzle – Regional event 2003

Level 3

ENONCE

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*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*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*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 retourner 1 s'il est possible de placer la pièce, 0 sinon.

CONTRAINTES

ENTREE

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

  • Les dix lignes suivantes décrivent l'état actuel du puzzle. Chaque ligne contient dix chiffres, parmi 0 et 1, sans espaces.

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.

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
250 milliseconds

Input/output samples

Sample input
0110
0110
1111
0011
1111111111
1110111111
1100111001
1100111001
1000011101
1100011111
1111011111
1100100111
1110110011
1110111111
Sample output
1

Submit your solution

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