Farmer John veut mieux décorer sa maison. Dans une boutique de porcelaine, il trouve une délicate figurine de vache en verre et décide de l’acheter pour le manteau de sa cheminée.
Sa forme est une grille de $N \times M$ caractères ($3 \leq N, M \leq 500$), comme ci-dessous. Les minuscules sont les parties de la figurine et leurs couleurs ; les . n’en font pas partie.
............... ............... x..x........... xxxx........... xxxxaaaaaaa... .xx.aaaaaaaaa.. ....aaaaaaa.aa. ....ll...ll.... ....vv...vv.... ...............
Juste avant l’achat, un taureau traverse la boutique, cassant la figurine et bien d’autres objets en verre sur les étagères ! Elle se brise en 3 morceaux, perdus parmi $K$ morceaux au sol ($4 \leq K \leq 100$). Chacun des $K$ morceaux est décrit par une grille, comme la figurine.
Trouvez le nombre d’ensembles de 3 morceaux parmi les $K$ pouvant être recollés pour reconstituer la figurine.
Les morceaux peuvent avoir été retournés verticalement ou horizontalement, ou tournés d’un multiple de 90 degrés. À partir de l’original et des $K$ grilles, cherchez les ensembles de 3 morceaux formant l’image, en autorisant translations, retournements et rotations de multiples de 90 degrés. Superposés, les 3 morceaux doivent former exactement l’original, chaque case colorée appartenant à exactement un morceau.
Entrée
La première ligne contient l’entier $K$. Suivent $K + 1$ descriptions : la première pour la figurine originale, les $K$ suivantes pour les morceaux.
Chaque description commence par les entiers $R$ et $C$ ($1 \le R, C \le 100$). Les $R$ lignes suivantes contiennent $C$ minuscules décrivant les couleurs. Chaque morceau est connexe par adjacence horizontale ou verticale et contient au moins une case non vide.
Sortie
Affichez le nombre de triplets $i, j, k$ ($i < j < k$) tels que les morceaux $i$, $j$ et $k$ puissent former la vache originale.
Exemples
Entrée 1
5 5 5 aaaaa ..a.. bbabb ..a.. aaaaa 3 5 ..abb ..a.. aaaaa 5 2 a. a. aa a. a. 1 2 bb 1 5 bbabb 2 5 aaaaa ..a..
Sortie 1
3
Remarque
Les trois solutions utilisent $(0, 1, 2)$, $(0, 2, 4)$ et $(1, 3, 4)$.
La limite de temps est de 6 secondes par cas de test, et du double pour Java et Python.
Auteur : Brian Dean