$10$ rivin ja $9$ sarakkeen kokoisella shakkilaudalla pelataan peliä nimeltä ”Qi Men Xiang Qi”. Kummallakin osapuolella on useita nappuloita, ja eri nappuloilla on erilaisia ominaisuuksia. Käytämme koordinaatteja $(x, y)$ esittämään sijaintia shakkilaudan $x$-nnellä rivillä ja $y$-nnessä sarakkeessa.
Meidän puolellamme on useita Torneja (Rooks) ja useita Ratsuja (Knights) sekä taito Muodonmuutos (Shape-shifting). Näiden kahden nappulatyypin liikkumistavat ja taito on kuvattu seuraavasti:
- Oletetaan, että Torni sijaitsee koordinaateissa $(a, b)$. Jos se siirtyy yhdellä toiminnolla shakkilaudan koordinaatteihin $(c, d)$, seuraavien ehtojen on täytyttävä:
- Koordinaateissa $(c, d)$ ei ole omia nappuloita. Toisin sanoen se ei voi lyödä omia nappuloita eikä mennä päällekkäin omien nappuloiden kanssa.
- $c = a$ tai $d = b$, mutta $(a, b) \neq (c, d)$. Toisin sanoen se voi liikkua sitä riviä tai saraketta pitkin, jolla se on, mutta ei voi jäädä paikalleen.
- Koordinaattien $(a, b)$ ja $(c, d)$ välissä ei saa olla mitään muita nappuloita. Toisin sanoen se ei voi hypätä muiden nappuloiden yli liikkuessaan.
- Oletetaan, että Ratsu sijaitsee koordinaateissa $(a, b)$. Jos se siirtyy yhdellä toiminnolla shakkilaudan koordinaatteihin $(c, d)$, seuraavien ehtojen on täytyttävä:
- Koordinaateissa $(c, d)$ ei ole omia nappuloita. Toisin sanoen se ei voi lyödä omia nappuloita eikä mennä päällekkäin omien nappuloiden kanssa.
- $\{|a - c|, |b - d|\} = \{1, 2\}$. Tässä $\{\dots\}$ tarkoittaa järjestämätöntä joukkoa. Tämä vastaa perinteisen shakin ”L”-kirjaimen muotoista siirtoa (huomaa, että tässä tehtävässä ratsun kulkua ei voi tukkia).
- Muodonmuutos: Tätä voidaan käyttää yhtenä toimintona minkä tahansa kahden oman nappulan paikkojen vaihtamiseen keskenään. Käyttökertojen määrää ei ole rajoitettu.
Vihollisella on useita Limoja (Slimes). Limat eivät voi liikkua, mutta niillä on seuraavat ominaisuudet:
- Oletetaan, että Lima sijaitsee koordinaateissa $(a, b)$. Kun se lyödään ja poistetaan laudalta, se jakautuu välittömästi luoden yhden Liman kuhunkin neljästä viereisestä ruudusta (ylös, alas, vasemmalle, oikealle). Tarkemmin sanottuna näihin neljään viereiseen ruutuun ei synny uusia limoja ruutuihin, joissa on jo jokin muu nappula tai jotka ovat shakkilaudan ulkopuolella.
- Jakautumisen kautta syntyneillä Limoilla on samat jakautumisominaisuudet, eikä jakautumisten määrää ole rajoitettu.
Kun nappuloita on siirretty ja ne menevät päällekkäin vihollisnappuloiden kanssa, tapahtuu lyönti, joka poistaa vihollisnappulat. Pelin voittoehdot täyttyvät, kun kaikki vihollisen Limat on lyöty eikä shakkilaudalla ole enää yhtään vihollisnappulaa.
Pelatessaan peliä Xiao Biao huomasi, että vaikka vihollinen ei voi liikuttaa nappuloitaan, meidän puolemme on silti vaikea lyödä kaikkia Limoja puhtaasti, sillä niitä on paljon ja ne jakautuvat erittäin tehokkaasti, mikä usein johtaa vain entistä useampien limojen syntymiseen ja tekee Xiao Biaolle vaikeaksi päätellä, onko voitto tässä pelissä mahdollinen. Hän on kääntynyt sinun puoleesi, koska olet taitava strategiassa ja analysoinnissa, ja toivoo sinun auttavan häntä selvittämään, onko olemassa strategiaa voiton saavuttamiseksi korkeintaan $10^4$ siirrossa. Jos tällainen voittostrategia on olemassa, tulosta kunkin vaiheen toiminnot.
Syöte
Syöte koostuu $10$ rivistä, joista jokainen sisältää pituutta $9$ olevan merkkijonon, joka kuvaa shakkilaudan tilannetta. Merkki . kuvaa tyhjää ruutua; merkki C kuvaa meidän Torniamme; merkki M kuvaa meidän Ratsuamme; ja merkki S kuvaa vihollisen Limaa.
Kutakin merkkiä voi esiintyä useita kertoja. Syöte takaa, että shakkilaudalla on vähintään yksi Lima ja vähintään yksi oma nappula.
Tuloste
Jos ei ole olemassa strategiaa, jolla voisi voittaa korkeintaan $10^4$ siirrossa:
- Tulosta yhdelle riville merkkijono
WuJie.
Jos on olemassa strategia, jolla voi voittaa korkeintaan $10^4$ siirrossa:
- Tulosta ensin yhdelle riville merkkijono
YouJie. - Tulosta seuraavaksi kokonaisluku $s$, joka kuvaa toimintojen lukumäärää.
- Tulosta sitten $s$ riviä, joista jokainen sisältää neljä kokonaislukua $a, b, c, d$, mikä ilmaisee, että tällä hetkellä ruudussa $(a, b)$ oleva oma nappula siirretään ruutuun $(c, d)$. Erityisesti, jos molemmissa ruuduissa $(a, b)$ ja $(c, d)$ on jo oma nappula, tämä toiminto katsotaan Muodonmuutokseksi, mikä tarkoittaa, että nämä kaksi nappulaa vaihtavat paikkoja.
- Strategiasi on varmistettava, että kaikkien toimintojen jälkeen shakkilaudalla ei ole yhtään Limaa jäljellä.
Jos kelvollisia ratkaisuja on useita, voit tulostaa niistä minkä tahansa.
Ratkaisut, jotka eivät täytä muotovaatimuksia, eivät noudata nappuloiden liikkumissääntöjä tai osoittavat ruutuun $(a, b)$, jossa ei ole nappulaa, katsotaan virheellisiksi.
Esimerkit
Syöte 1
...CSC... ...CCCM.. ......... ......... ......... ......... ......... ......... ......... .........
Tuloste 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
Syöte 2
SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSCSSSS
Tuloste 2
WuJie
Huomautus
Esimerkin $1$ tuloste esittelee useita kelvollisia toimintoja ja lyö lopulta kaikki limat.
- Vaiheet $1$–$3$ näyttävät ruudussa $(1, 4)$ olevan Tornin liikkuvan vasemmalle ruutu kerrallaan ja päätyvän lopulta ruutuun $(1, 1)$.
- Vaihe $4$ esittelee Muodonmuutos-toiminnon, joka vaihtaa ruudussa $(1, 1)$ olevan Tornin ja ruudussa $(2, 4)$ olevan Tornin paikat.
- Vaihe $5$ näyttää ruudussa $(2, 4)$ olevan Tornin liikkuvan ylös ruutuun $(1, 4)$.
- Viimeinen vaihe näyttää Ratsun hyppäävän ruudusta $(2, 7)$ ruutuun $(1, 5)$ lyödäkseen ainoan Liman. Koska Liman vieressä ei tämän jälkeen ole kelvollisia tyhjiä ruutuja, se ei voi jakautua. Peli on voitettu.