Sur un échiquier de $10$ lignes par $9$ colonnes, un jeu appelé « Qi Men Xiang Qi » est en cours. Chaque camp possède plusieurs pièces, et des pièces différentes ont des caractéristiques différentes. Nous utilisons les coordonnées $(x, y)$ pour représenter la position à la $x$-ième ligne et la $y$-ième colonne de l'échiquier.
Notre camp possède plusieurs Tours (Rooks) et plusieurs Cavaliers (Knights), ainsi que la compétence Métamorphose (Shape-shifting). Les méthodes de déplacement de ces deux types de pièces et la compétence sont décrites comme suit :
- Supposons que la Tour soit située aux coordonnées $(a, b)$. Si elle se déplace aux coordonnées $(c, d)$ sur l'échiquier en une seule action, les conditions suivantes doivent être remplies :
- Il n'y a aucune pièce alliée en $(c, d)$. C'est-à-dire qu'elle ne peut pas capturer de pièces alliées, ni se superposer à des pièces alliées.
- $c = a$ ou $d = b$, mais $(a, b) \neq (c, d)$. C'est-à-dire qu'elle peut se déplacer le long de la ligne ou de la colonne où elle se trouve, mais ne peut pas rester sur place.
- Il ne peut y avoir aucune autre pièce entre $(a, b)$ et $(c, d)$. C'est-à-dire qu'elle ne peut pas sauter par-dessus d'autres pièces lors de son déplacement.
- Supposons que le Cavalier soit situé aux coordonnées $(a, b)$. S'il se déplace aux coordonnées $(c, d)$ sur l'échiquier en une seule action, les conditions suivantes doivent être remplies :
- Il n'y a aucune pièce alliée en $(c, d)$. C'est-à-dire qu'il ne peut pas capturer de pièces alliées, ni se superposer à des pièces alliées.
- $\{|a - c|, |b - d|\} = \{1, 2\}$. Ici, $\{\dots\}$ désigne un ensemble non ordonné. Cela correspond au déplacement traditionnel aux échecs en forme de « L » (notez qu'il n'y a pas d'obstacle bloquant le cavalier dans ce problème).
- Métamorphose : Peut être utilisée comme une action pour échanger les positions de deux pièces alliées quelconques. Il n'y a aucune limite au nombre d'utilisations.
L'ennemi possède plusieurs Slimes. Les Slimes ne peuvent pas se déplacer mais ont les caractéristiques suivantes :
- Supposons que le Slime soit situé aux coordonnées $(a, b)$. Lorsqu'il est capturé et retiré, il se divise immédiatement, générant un Slime dans chacune des quatre positions adjacentes (haut, bas, gauche, droite). Plus précisément, parmi ces quatre positions adjacentes, aucun nouveau slime ne sera généré dans les positions qui contiennent déjà une autre pièce ou qui sont hors des limites de l'échiquier.
- Les Slimes générés par division ont les mêmes caractéristiques de division et il n'y a pas de limite au nombre de divisions.
Après le déplacement des pièces, si elles se superposent à des pièces ennemies, cela déclenche une capture, retirant les pièces ennemies. La condition de victoire du jeu est de capturer tous les Slimes ennemis, en s'assurant qu'il ne reste plus aucune pièce ennemie sur l'échiquier.
En jouant, Xiao Biao a constaté que bien que l'ennemi ne puisse pas déplacer ses pièces, il reste difficile pour notre camp de capturer proprement les Slimes, car ils sont nombreux et se divisent très efficacement, ce qui conduit souvent à la génération de plus de slimes et rend difficile pour Xiao Biao de déterminer si la victoire est possible dans cette partie. Il s'est tourné vers vous, qui êtes doué en stratégie et en analyse, en espérant que vous pourrez l'aider à déterminer s'il existe une stratégie permettant d'obtenir la victoire en au plus $10^4$ coups. Si une telle stratégie gagnante existe, veuillez afficher les opérations pour chaque étape.
Entrée
L'entrée se compose de $10$ lignes, contenant chacune une chaîne de caractères de longueur $9$, représentant la situation de l'échiquier. Le caractère . représente une position vide ; le caractère C représente notre Tour ; le caractère M représente notre Cavalier ; et le caractère S représente le Slime ennemi.
Chaque type de caractère peut apparaître plusieurs fois. Les données garantissent qu'il y a au moins un Slime sur l'échiquier et au moins une pièce alliée.
Sortie
S'il n'existe aucune stratégie pour gagner en au plus $10^4$ coups :
- Veuillez afficher sur une seule ligne la chaîne
WuJie.
S'il existe une stratégie pour gagner en au plus $10^4$ coups :
- Tout d'abord, affichez sur une seule ligne la chaîne
YouJie. - Ensuite, affichez un entier $s$, représentant le nombre d'actions.
- Puis, affichez $s$ lignes, contenant chacune quatre entiers $a, b, c, d$, indiquant que la pièce alliée actuellement en $(a, b)$ est déplacée vers la position $(c, d)$. Plus précisément, si les deux positions $(a, b)$ et $(c, d)$ contiennent déjà des pièces alliées, cette action est considérée comme une Métamorphose, indiquant que ces deux pièces échangent leurs positions.
- Votre stratégie doit garantir qu'une fois toutes les actions terminées, il ne reste plus aucun Slime sur l'échiquier.
S'il existe plusieurs solutions valides différentes, n'importe laquelle d'entre elles peut être affichée.
Les solutions qui ne respectent pas les exigences de format, qui ne se conforment pas aux règles de déplacement des pièces ou qui indiquent une position $(a, b)$ où il n'y a pas de pièce seront considérées comme incorrectes.
Exemples
Entrée 1
...CSC... ...CCCM.. ......... ......... ......... ......... ......... ......... ......... .........
Sortie 1
YouJie 6 1 4 1 3 1 3 1 2 1 2 1 1 1 1 2 4 2 4 1 4 2 7 1 5
Entrée 2
SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSCSSSS
Sortie 2
WuJie
Note
La sortie de l'exemple $1$ montre plusieurs opérations valides et capture finalement tous les slimes.
- Les étapes $1$ à $3$ montrent la Tour en $(1, 4)$ se déplaçant vers la gauche, choisissant d'avancer d'une case à la fois, pour finalement atterrir en $(1, 1)$.
- L'étape $4$ montre l'opération de Métamorphose, échangeant la Tour en $(1, 1)$ avec la Tour en $(2, 4)$.
- L'étape $5$ montre la Tour en $(2, 4)$ montant en $(1, 4)$.
- La dernière étape montre le Cavalier sautant de $(2, 7)$ à $(1, 5)$ pour capturer l'unique Slime. Comme il n'y a aucune position vide valide adjacente au Slime après cela, il ne peut pas se diviser. La partie est gagnée.