L'objectif de ce problème est de déterminer si deux configurations de formes bidimensionnelles, définies sur une grille, sont équivalentes. L'équivalence est définie par la possibilité d'établir une correspondance biunivoque entre les composantes connexes (souvent appelées "pièces" ou "clusters") de chaque configuration. Chaque paire de pièces correspondantes doit pouvoir coïncider après une combinaison d'opérations géométriques : translation, rotation (par multiples de 90 degrés) et réflexion (miroir).
Il est crucial de noter que ce problème ne se réduit pas à une simple vérification d'isomorphisme de graphes. Bien que l'isomorphisme de graphes soit une condition nécessaire, il n'est pas suffisant. Par exemple, deux formes peuvent avoir la même structure de connectivité (même graphe sous-jacent) mais être impossibles à superposer via les transformations permises en raison de leur disposition spatiale spécifique sur la grille. Considérons l'exemple suivant illustrant deux groupes de cellules connectées qui sont isomorphes en tant que graphes, mais non superposables géométriquement sur une grille 2D via les transformations autorisées :
Configuration A: Configuration B:
. X . . . X
X X . . X X
. . . . . .
Dans cet exemple, la configuration A est un "L" orienté vers le haut-gauche. La configuration B est également un "L", mais orienté différemment. Bien que les deux formes soient constituées de trois cellules connectées, et que leurs graphes sous-jacents soient des chemins de longueur 2 (P3), la configuration B ne peut pas être obtenue à partir de la configuration A par des rotations de 90 degrés, des réflexions ou des translations. La nature des arêtes (horizontales ou verticales) est essentielle pour ces transformations. L'isomorphisme de graphes ne prend pas en compte cette information spatiale.
La stratégie de résolution implique les étapes suivantes :
- Identifier toutes les composantes connexes (ensembles de cellules adjacentes) dans la premmière configuration.
- Identifier toutes les composantes connexes dans la deuxième configuration.
- Pour chaque composante de la première configuration, tenter de trouver une composante correspondante dans la deuxième configuration. Cette recherche doit prendre en compte toutes les transformations géométriques possibles (rotations de 0, 90, 180, 270 degrés, combinées à des réflexions horizontales et verticales).
- Assurer que la correspondance est biunivoque : chaque composante de la première configuration doit être appariée avec une unique composante de la seconde, et toutes les composantes doivent être appariées.
L'implémentation de cette approche nécessite des fonctions pour extraire les composantes (généralement via un algorithme de Flood-Fill), les normaliser pour faciliter la comparaison, et appliquer les transformations géométriques.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring> // Pour la fonction memset
// Représente une coordonnée (ligne, colonne) sur la grille
struct Coordonnee {
int ligne, colonne;
Coordonnee(int l = 0, int c = 0) : ligne(l), colonne(c) {}
// Surcharge de l'opérateur < pour permettre le tri des points dans une composante.
// Cela crée une forme "canonique" de la composante relative à son premier point.
bool operator<(const Coordonnee& autre) const {
if (ligne != autre.ligne) return ligne < autre.ligne;
return colonne < autre.colonne;
}
};
// Dimensions de la grille et nombre de points initialement activés
int HAUTEUR, LARGEUR, NB_POINTS_INITIAUX;
// Grille temporaire utilisée par l'algorithme de Flood-Fill pour marquer les cellules visitées
int grilleTemporaire[110][110];
// Déplacements pour les 4 directions cardinales (haut, gauche, bas, droite)
int deplacements[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
// Vecteurs pour stocker les ensembles de composantes connexes pour les deux cartes
std::vector<std::vector<Coordonnee>> composantesCarteGauche, composantesCarteDroite;
// Vecteur temporaire pour construire une composante lors du parcours DFS
std::vector<Coordonnee> composanteEnCours;
// Algorithme de Flood-Fill (DFS) pour trouver et extraire une composante connexe
void parcourirComposante(int l, int c) {
composanteEnCours.push_back(Coordonnee(l, c));
grilleTemporaire[l][c] = 0; // Marque la cellule comme visitée (ou inactive)
for (int k = 0; k < 4; ++k) {
int nouvelleL = l + deplacements[k][0];
int nouvelleC = c + deplacements[k][1];
// Vérifie si la nouvelle coordonnée est dans les limites de la grille et active
if (nouvelleL >= 0 && nouvelleL < HAUTEUR &&
nouvelleC >= 0 && nouvelleC < LARGEUR &&
grilleTemporaire[nouvelleL][nouvelleC]) {
parcourirComposante(nouvelleL, nouvelleC);
}
}
}
// Applique une rotation de 90 degrés dans le sens anti-horaire à une composante.
// La rotation est effectuée autour du premier point de la composante triée.
std::vector<Coordonnee> appliquerRotation90CCW(const std::vector<Coordonnee>& comp) {
std::vector<Coordonnee> compRotated;
if (comp.empty()) return compRotated;
int pivotL = comp.front().ligne;
int pivotC = comp.front().colonne;
for (const auto& p : comp) {
// Transformation pour une rotation anti-horaire de 90 degrés autour (pivotL, pivotC):
// (x', y') = (pivotX - (y - pivotY), pivotY + (x - pivotX))
compRotated.push_back(Coordonnee(pivotL - (p.colonne - pivotC), pivotC + (p.ligne - pivotL)));
}
std::sort(compRotated.begin(), compRotated.end()); // Conserve la forme canonique
return compRotated;
}
// Applique une réflexion horizontale (gauche-droite) à une composante.
// La réflexion est effectuée par rapport à la colonne du premier point de la composante triée.
std::vector<Coordonnee> appliquerReflexionHorizontale(const std::vector<Coordonnee>& comp) {
std::vector<Coordonnee> compReflected;
if (comp.empty()) return compReflected;
int axeC = comp.front().colonne; // Axe de réflexion vertical (x = axeC)
for (const auto& p : comp) {
// x' = 2*axeC - x, y' = y
compReflected.push_back(Coordonnee(p.ligne, 2 * axeC - p.colonne));
}
std::sort(compReflected.begin(), compReflected.end());
return compReflected;
}
// Applique une réflexion verticale (haut-bas) à une composante.
// La réflexion est effectuée par rapport à la ligne du premier point de la composante triée.
std::vector<Coordonnee> appliquerReflexionVerticale(const std::vector<Coordonnee>& comp) {
std::vector<Coordonnee> compReflected;
if (comp.empty()) return compReflected;
int axeL = comp.front().ligne; // Axe de réflexion horizontal (y = axeL)
for (const auto& p : comp) {
// x' = x, y' = 2*axeL - y
compReflected.push_back(Coordonnee(2 * axeL - p.ligne, p.colonne));
}
std::sort(compReflected.begin(), compReflected.end());
return compReflected;
}
// Vérifie si deux composantes sont identiques après une translation arbitraire.
// Les composantes doivent être triées pour que cette comparaison fonctionne.
bool sontIdentiquesApresTranslation(const std::vector<Coordonnee>& c1, const std::vector<Coordonnee>& c2) {
if (c1.size() != c2.size() || c1.empty()) return false;
// Calcule le décalage nécessaire pour aligner les premiers points
int decalageL = c1.front().ligne - c2.front().ligne;
int decalageC = c1.front().colonne - c2.front().colonne;
// Vérifie si tous les autres points respectent ce même décalage
for (size_t i = 1; i < c1.size(); ++i) {
if (c1[i].ligne - c2[i].ligne != decalageL ||
c1[i].colonne - c2[i].colonne != decalageC) {
return false;
}
}
return true;
}
// Vérifie si la composante A peut coïncider avec la composante B via n'importe quelle
// combinaison de rotation (0, 90, 180, 270 degrés), réflexion (horizontale, verticale) et translation.
bool peutCorrespondreParTransformations(std::vector<Coordonnee> compA, const std::vector<Coordonnee>& compB) {
if (compA.size() != compB.size()) return false;
// Vérifie l'état original et ses réflexions
if (sontIdentiquesApresTranslation(compA, compB)) return true;
if (sontIdentiquesApresTranslation(appliquerReflexionHorizontale(compA), compB)) return true;
if (sontIdentiquesApresTranslation(appliquerReflexionVerticale(compA), compB)) return true;
// Applique 3 rotations supplémentaires de 90 degrés (pour 90, 180, 270 degrés)
for (int i = 0; i < 3; ++i) {
compA = appliquerRotation90CCW(compA); // Nouvelle forme après rotation
if (sontIdentiquesApresTranslation(compA, compB)) return true;
if (sontIdentiquesApresTranslation(appliquerReflexionHorizontale(compA), compB)) return true;
if (sontIdentiquesApresTranslation(appliquerReflexionVerticale(compA), compB)) return true;
}
return false;
}
// Comparateur pour trier les vecteurs de composantes par leur taille (nombre de points)
bool comparerVecteursComposantesParTaille(const std::vector<Coordonnee>& c1, const std::vector<Coordonnee>& c2) {
return c1.size() < c2.size();
}
int main() {
// Optimisation des opérations d'entrée/sortie en C++
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int nombreDeCas;
std::cin >> nombreDeCas;
while (nombreDeCas--) {
composantesCarteGauche.clear();
composantesCarteDroite.clear();
std::cin >> LARGEUR >> HAUTEUR >> NB_POINTS_INITIAUX;
// --- Traitement de la carte de gauche ---
std::memset(grilleTemporaire, 0, sizeof(grilleTemporaire)); // Réinitialise la grille
for (int i = 0; i < NB_POINTS_INITIAUX; ++i) {
int x, y;
std::cin >> x >> y;
grilleTemporaire[y][x] = 1; // Stockage des points actifs (y=ligne, x=colonne)
}
// Extrait toutes les composantes connexes de la grille de gauche
for (int l = 0; l < HAUTEUR; ++l) {
for (int c = 0; c < LARGEUR; ++c) {
if (grilleTemporaire[l][c]) { // Si la cellule est active et non visitée
composanteEnCours.clear();
parcourirComposante(l, c); // Lance le Flood-Fill
std::sort(composanteEnCours.begin(), composanteEnCours.end()); // Normalise la composante
composantesCarteGauche.push_back(composanteEnCours);
}
}
}
// --- Traitement de la carte de droite ---
std::memset(grilleTemporaire, 0, sizeof(grilleTemporaire)); // Réinitialise la grille
for (int i = 0; i < NB_POINTS_INITIAUX; ++i) {
int x, y;
std::cin >> x >> y;
grilleTemporaire[y][x] = 1;
}
// Extrait toutes les composantes connexes de la grille de droite
for (int l = 0; l < HAUTEUR; ++l) {
for (int c = 0; c < LARGEUR; ++c) {
if (grilleTemporaire[l][c]) {
composanteEnCours.clear();
parcourirComposante(l, c);
std::sort(composanteEnCours.begin(), composanteEnCours.end());
composantesCarteDroite.push_back(composanteEnCours);
}
}
}
// Si le nombre de composantes diffère, les cartes ne peuvent pas être équivalentes
if (composantesCarteGauche.size() != composantesCarteDroite.size()) {
std::cout << "NO\n";
continue;
}
// Trie les listes de composantes par leur taille. Cela permet d'optimiser la recherche
// en comparant d'abord les composantes de même taille.
std::sort(composantesCarteGauche.begin(), composantesCarteGauche.end(), comparerVecteursComposantesParTaille);
std::sort(composantesCarteDroite.begin(), composantesCarteDroite.end(), comparerVecteursComposantesParTaille);
bool toutesLesComposantesOntTrouveUneCorrespondance = true;
// Tente d'apparier chaque composante de la carte de gauche avec une de la carte de droite
while (!composantesCarteGauche.empty()) {
// Si la plus petite composante de gauche n'a pas la même taille que la plus petite de droite,
// alors aucune correspondance n'est possible (car les listes sont triées par taille).
if (composantesCarteGauche.front().size() != composantesCarteDroite.front().size()) {
toutesLesComposantesOntTrouveUneCorrespondance = false;
break;
}
bool correspondanceTrouveePourComposanteActuelle = false;
// Parcourt les composantes de droite pour trouver une correspondance
for (size_t i = 0; i < composantesCarteDroite.size(); ++i) {
// Arrête la recherche si la taille de la composante droite est déjà supérieure
// à celle de la composante gauche actuelle (optimisation due au tri).
if (composantesCarteDroite[i].size() > composantesCarteGauche.front().size()) {
break;
}
if (peutCorrespondreParTransformations(composantesCarteGauche.front(), composantesCarteDroite[i])) {
correspondanceTrouveePourComposanteActuelle = true;
// Retire les deux composantes pour éviter de les réutiliser
composantesCarteGauche.erase(composantesCarteGauche.begin());
composantesCarteDroite.erase(composantesCarteDroite.begin() + i);
break; // Passe à la composante suivante de la carte gauche
}
}
if (!correspondanceTrouveePourComposanteActuelle) {
toutesLesComposantesOntTrouveUneCorrespondance = false;
break;
}
}
std::cout << (toutesLesComposantesOntTrouveUneCorrespondance ? "YES\n" : "NO\n");
}
return 0;
}