Problème du Mur Hamiltonien
Énoncé du problème
On vous donne une matrice $2\times m$ qui ne contient que les caractères B et W. Chaque colonne contient au moins un caractère B. La question est de savoir s'il existe un chemin qui satisfait les conditions suivantes :
- Les cellules adjacentes dans le chemin partagent un côté commun (pas seulement un coin).
- Chaque cellule
Best visitée exactement une fois. - Aucune cellule
Wn'est visitée.
Si un tel chemin existe, on doit afficher YES, sinon NO.
Description du problème
Sir Monocarp Hamilton prévoit de peindre son mur. Le mur peut être représenté comme une grille de $2$ lignes et $m$ colonnes. Initialement, le mur est entièrement blanc.
Monocarp souhaite peindre une image noire sur le mur. Plus précisément, il veut que la cellule $(i, j)$ (la $j$-ème cellule de la $i$-ème ligne) soit colorée en noir si $c_{i, j} =$ 'B', et laissée blanche si $c_{i, j} =$ 'W'. De plus, il veut que chaque colonne ait au moins une cellule noire, donc pour chaque $j$, la contrainte suivante est satisfaite : $c_{1, j}$, $c_{2, j}$ ou les deux sont égaux à 'B'.
Pour que l'image soit lisse, Monocarp veut placer un pinceau dans une certaine cellule $(x_1, y_1)$ et le déplacer le long du chemin $(x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)$ de telle sorte que :
- pour chaque $i$, $(x_i, y_i)$ et $(x_{i+1}, y_{i+1})$ partagent un côté commun ;
- toutes les cellules noires aparaissent dans le chemin exactement une fois ;
- les cellules blanches n'apparaissent pas dans le chemin.
Déterminez si Monocarp peut peindre le mur.
Format d'entrée
La première ligne contient un seul entier $t$ ($1 \le t \le 10^4$) — le nombre de cas de test.
La première ligne de chaque cas de test contient un seul entier $m$ ($1 \le m \le 2 \cdot 10^5$) — le nombre de colonnes du mur.
L'une des deux lignes suivantes contient une chaîne $c_i$, composée de $m$ caractères, où chaque caractère est soit 'B', soit 'W'. $c_{i, j}$ est 'B' si la cellule $(i, j)$ doit être colorée en noir, et 'W' si la cellule $(i, j)$ doit rester blanche.
De plus, pour chaque $j$, la contrainte suivante est satisfaite : $c_{1, j}$, $c_{2, j}$ ou les deux sont égaux à 'B'.
La some de $m$ sur tous les cas de test ne dépasse pas $2 \cdot 10^5$.
Format de sortie
Pour chaque cas de test, affichez "YES" si Monocarp peut peindre le mur. Sinon, affichez "NO".
Exemple #1
Exemple d'entrée #1
6
3
WBB
BBW
1
B
B
5
BWBWB
BBBBB
2
BW
WB
5
BBBBW
BWBBB
6
BWBBWB
BBBBBB
Exemple de sortie #1
YES
YES
NO
NO
NO
YES
Explications
Dans le premier cas de test, Monocarp peut suivre le chemin $(2, 1)$, $(2, 2)$, $(1, 2)$, $(1, 3)$ avec son pinceau. Toutes les cellules noires apparaisssent dans le chemin exactement une fois, et aucune cellule blanche n'apparaît dans le chemin.
Dans le deuxième cas de test, Monocarp peut suivre le chemin $(1, 1)$, $(2, 1)$.
Dans le troisième cas de test :
- le chemin $(1, 1)$, $(2, 1)$, $(2, 2)$, $(2, 3)$, $(1, 3)$, $(2, 4)$, $(2, 5)$, $(1, 5)$ n'est pas valide car les cellules $(1, 3)$ et $(2, 4)$ ne partagent pas un côté commun ;
- le chemin $(1, 1)$, $(2, 1)$, $(2, 2)$, $(2, 3)$, $(1, 3)$, $(2, 3)$, $(2, 4)$, $(2, 5)$, $(1, 5)$ n'est pas valide car la cellule $(2, 3)$ est visitée deux fois ;
- le chemin $(1, 1)$, $(2, 1)$, $(2, 2)$, $(2, 3)$, $(2, 4)$, $(2, 5)$, $(1, 5)$ n'est pas valide car la cellule noire $(1, 3)$ n'apparaît pas dans le chemin ;
- le chemin $(1, 1)$, $(2, 1)$, $(2, 2)$, $(2, 3)$, $(2, 4)$, $(2, 5)$, $(1, 5)$, $(1, 4)$, $(1, 3)$ n'est pas valide car la cellule blanche $(1, 4)$ apparaît dans le chemin.
// Solution pour le problème du Mur Hamiltonien
// Approche par parcours en profondeur d'abord (DFS)
// On commence à partir de la colonne la plus à gauche
// On essaie de visiter toutes les cellules 'B' exactement une fois
// Si on y parvient, on retourne YES, sinon NO
#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e5 + 3;
string grille[2];
int nbColonnes;
bool visite[2][MAX];
int nbCasesNoires;
bool parcoursProfondeur(int ligne, int colonne, int compteur)
{
if (compteur == nbCasesNoires) return true;
// Déplacements possibles : droite, gauche, haut/bas
int deplacementsL[] = {0, 0, 1, -1};
int deplacementsC[] = {1, -1, 0, 0};
for (int i = 0; i < 4; i++) {
int nouvLigne = ligne + deplacementsL[i];
int nouvColonne = colonne + deplacementsC[i];
if (nouvLigne >= 0 && nouvLigne <= 1 &&
nouvColonne >= 0 && nouvColonne < nbColonnes &&
!visite[nouvLigne][nouvColonne] &&
grille[nouvLigne][nouvColonne] == 'B') {
visite[nouvLigne][nouvColonne] = true;
if (parcoursProfondeur(nouvLigne, nouvColonne, compteur + 1)) return true;
visite[nouvLigne][nouvColonne] = false;
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int nbTests;
cin >> nbTests;
while (nbTests--) {
cin >> nbColonnes;
nbCasesNoires = 0;
bool solutionTrouvee = false;
cin >> grille[0] >> grille[1];
// Compter le nombre de cases noires
for (int i = 0; i < nbColonnes; ++i) {
if (grille[0][i] == 'B') nbCasesNoires++;
if (grille[1][i] == 'B') nbCasesNoires++;
}
// Réinitialiser le tableau de visite
for (int i = 0; i < nbColonnes; i++) {
visite[0][i] = false;
visite[1][i] = false;
}
// Essayer de commencer depuis la première ligne, première colonne
if (grille[0][0] == 'B') {
visite[0][0] = true;
if (parcoursProfondeur(0, 0, 1)) {
cout << "YES" << endl;
solutionTrouvee = true;
}
}
// Si pas trouvé, essayer de commencer depuis la deuxième ligne, première colonne
if (!solutionTrouvee && grille[1][0] == 'B') {
// Réinitialiser le tableau de visite
for (int i = 0; i < nbColonnes; i++) {
visite[0][i] = false;
visite[1][i] = false;
}
visite[1][0] = true;
if (parcoursProfondeur(1, 0, 1)) {
cout << "YES" << endl;
solutionTrouvee = true;
}
}
if (!solutionTrouvee) cout << "NO" << endl;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6 + 10;
string grille[2];
int nbColonnes;
bool estValide(int depart)
{
bool positionActuelle = depart;
if (grille[positionActuelle][0] == 'B') positionActuelle = !positionActuelle;
for (int i = 1; i < nbColonnes; i++) {
if (grille[positionActuelle][i] == 'W') return false;
if (grille[!positionActuelle][i] == 'B') positionActuelle = !positionActuelle;
}
return true;
}
bool resoudre()
{
cin >> nbColonnes >> grille[0] >> grille[1];
if (grille[0][0] == 'B') {if (estValide(1)) return true;}
if (grille[1][0] == 'B') {if (estValide(0)) return true;}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int nbTests;
cin >> nbTests;
while (nbTests--) {
if (resoudre()) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}