På et sjakkbrett med $10$ rader og $9$ kolonner spilles et spill kalt «Qi Men Xiang Qi». Hver side har flere brikker, og ulike brikker har ulike egenskaper. Vi bruker koordinatene $(x, y)$ for å representere posisjonen i den $x$-te raden og den $y$-te kolonnen på sjakkbrettet.
Vår side har flere Tårn (Rooks) og flere Springere (Knights), samt ferdigheten Formskifte (Shape-shifting). Bevegelsesmetodene til disse to typene brikker og ferdigheten er beskrevet som følger:
- Anta at Tårnet befinner seg på koordinatene $(a, b)$. Hvis det flytter til koordinatene $(c, d)$ på sjakkbrettet i én handling, må følgende betingelser være oppfylt:
- Det er ingen egne brikker på $(c, d)$. Det vil si at det ikke kan slå egne brikker, og heller ikke overlappe med egne brikker.
- $c = a$ eller $d = b$, men $(a, b) \neq (c, d)$. Det vil si at det kan flytte langs raden eller kolonnen det står i, men kan ikke bli stående på samme posisjon.
- Det kan ikke være noen andre brikker mellom $(a, b)$ og $(c, d)$. Det vil si at det ikke kan hoppe over andre brikker mens det flytter.
- Anta at Springeren befinner seg på koordinatene $(a, b)$. Hvis den flytter til koordinatene $(c, d)$ på sjakkbrettet i én handling, må følgende betingelser være oppfylt:
- Det er ingen egne brikker på $(c, d)$. Det vil si at den ikke kan slå egne brikker, og heller ikke overlappe med egne brikker.
- $\{|a - c|, |b - d|\} = \{1, 2\}$. Her betegner $\{\dots\}$ en uordnet mengde. Dette tilsvarer den tradisjonelle sjakkbevegelsen i «L»-form (merk at det ikke er noen blokkering av springeren i denne oppgaven).
- Formskifte: Dette kan brukes som én handling for å bytte posisjonene til to vilkårlige egne brikker. Det er ingen grense for antall ganger det kan brukes.
Fienden har flere Slim (Slimes). Slim kan ikke bevege seg, men har følgende egenskaper:
- Anta at Slimet befinner seg på koordinatene $(a, b)$. Når det blir slått og fjernet, vil det umiddelbart dele seg og generere ett Slim i hver av de fire tilstøtende posisjonene (opp, ned, venstre, høyre). Mer spesifikt, i disse fire tilstøtende posisjonene vil det ikke genereres nye slim i posisjoner som allerede har andre brikker eller som er utenfor sjakkbrettets grenser.
- Slimene som genereres ved deling har de samme delingsegenskapene, og det er ingen grense for antall delinger.
Etter at brikkene er flyttet, vil de utløse et slag som fjerner fiendens brikker dersom de overlapper med dem. Seiersbetingelsen i spillet er å slå alle fiendens Slim, slik at det ikke er noen fiendtlige brikker igjen på sjakkbrettet.
Mens han spilte spillet, oppdaget Xiao Biao at selv om fienden ikke kan flytte brikkene sine, er det fortsatt vanskelig for vår side å slå ut Slimene rent, ettersom de er mange og deler seg svært effektivt, noe som ofte fører til at enda flere slim genereres og gjør det vanskelig for Xiao Biao å avgjøre om seier er mulig i dette spillet. Han har kommet til deg, som er dyktig i strategi og analyse, i håp om at du kan hjelpe ham med å avgjøre om det finnes en strategi for å oppnå seier innen $10^4$ trekk. Hvis en slik vinnende strategi finnes, vennligst skriv ut operasjonene for hvert steg.
Inndata
Inndataene består av $10$ linjer, som hver inneholder en streng med lengde $9$ som representerer situasjonen på sjakkbrettet. Tegnet . representerer en tom posisjon; tegnet C representerer vårt Tårn; tegnet M representerer vår Springer; og tegnet S representerer fiendens Slim.
Hver type tegn kan forekomme flere ganger. Dataene garanterer at det er minst ett Slim på sjakkbrettet og minst én egen brikke.
Utdata
Hvis det ikke finnes noen strategi for å vinne innen $10^4$ trekk:
- Skriv ut én enkelt linje med strengen
WuJie.
Hvis det finnes en strategi for å vinne innen $10^4$ trekk:
- Skriv først ut én enkelt linje med strengen
YouJie. - Deretter skriver du ut et heltall $s$, som representerer antallet handlinger.
- Skriv så ut $s$ linjer, som hver inneholder fire heltall $a, b, c, d$, som angir at den egne brikken som for øyeblikket står på $(a, b)$, flyttes til posisjon $(c, d)$. Spesifikt, hvis begge posisjonene $(a, b)$ og $(c, d)$ allerede har egne brikker, regnes denne handlingen som Formskifte, noe som angir at disse to brikkene bytter posisjon.
- Strategien din må sikre at det ikke er noen Slim igjen på sjakkbrettet etter at alle handlingene er fullført.
Hvis det finnes flere ulike gyldige løsninger, kan hvilken som helst av dem skrives ut.
Løsninger som ikke oppfyller formatkravene, ikke følger reglene for flytting av brikker, eller angir at det ikke står noen brikke på posisjon $(a, b)$, vil bli regnet som feil.
Eksempler
Inndata 1
...CSC... ...CCCM.. ......... ......... ......... ......... ......... ......... ......... .........
Utdata 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
Inndata 2
SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSCSSSS
Utdata 2
WuJie
Merk
Utdataene for eksempel $1$ viser flere gyldige operasjoner, og slår til slutt alle slimene.
- Steg $1$ til $3$ viser Tårnet på $(1, 4)$ som flytter mot venstre, velger å flytte én rute om gangen, og til slutt lander på $(1, 1)$.
- Steg $4$ viser Formskifte-operasjonen, der Tårnet på $(1, 1)$ bytter plass med Tårnet på $(2, 4)$.
- Steg $5$ viser Tårnet på $(2, 4)$ som flytter opp til $(1, 4)$.
- Det siste steget viser Springeren som hopper fra $(2, 7)$ til $(1, 5)$ for å slå det eneste Slimet. Siden det ikke er noen gyldige tomme posisjoner ved siden av Slimet etter dette, kan det ikke dele seg. Spillet er vunnet.