Á skákborði með $10$ röðum og $9$ dálkum er verið að spila leik sem kallast „Qi Men Xiang Qi“. Hvor hlið hefur nokkra taflmenn og ólíkir taflmenn hafa ólíka eiginleika. Við notum hnitin $(x, y)$ til að tákna stöðuna í $x$-tu röð og $y$-ta dálki skákborðsins.
Okkar hlið hefur nokkra Hróka (Rooks) og nokkra Riddara (Knights), ásamt hæfileikanum Hamskipti (Shape-shifting). Hreyfiaðferðum þessara tveggja tegunda taflmanna og hæfileikanum er lýst sem hér segir:
- Gerum ráð fyrir að Hrókurinn sé staðsettur í hnitunum $(a, b)$. Ef hann færir sig í hnitin $(c, d)$ á skákborðinu í einni aðgerð verða eftirfarandi skilyrði að vera uppfyllt:
- Engir vinveittir taflmenn eru á $(c, d)$. Það er að segja, hann getur ekki drepið vinveitta taflmenn né heldur skarast við vinveitta taflmenn.
- $c = a$ eða $d = b$, en $(a, b) \neq (c, d)$. Það er að segja, hann getur færst eftir röðinni eða dálknum sem hann er í, en getur ekki verið kyrr á sama stað.
- Engir aðrir taflmenn mega vera á milli $(a, b)$ og $(c, d)$. Það er að segja, hann getur ekki stokkið yfir aðra taflmenn á meðan hann hreyfist.
- Gerum ráð fyrir að Riddarinn sé staðsettur í hnitunum $(a, b)$. Ef hann færir sig í hnitin $(c, d)$ á skákborðinu í einni aðgerð verða eftirfarandi skilyrði að vera uppfyllt:
- Engir vinveittir taflmenn eru á $(c, d)$. Það er að segja, hann getur ekki drepið vinveitta taflmenn né heldur skarast við vinveitta taflmenn.
- $\{|a - c|, |b - d|\} = \{1, 2\}$. Hér táknar $\{\dots\}$ óraðað mengi. Þetta samsvarar hefðbundinni skákhreyfingu í „L“-lögun (athugið að það eru engar riddarahindranir í þessu verkefni).
- Hamskipti: Þetta má nota sem eina aðgerð til að víxla stöðum hvaða tveggja vinveittra taflmanna sem er. Engin takmörk eru á fjölda skipta sem hægt er að nota þetta.
Óvinurinn hefur nokkra Slímklessur (Slimes). Slímklessur geta ekki hreyft sig en hafa eftirfarandi eiginleika:
- Gerum ráð fyrir að Slímklessan sé staðsett í hnitunum $(a, b)$. Þegar hún er drepin og fjarlægð skiptir hún sér samstundis og býr til eina Slímklessu í hverri af fjórum aðliggjandi stöðum (upp, niður, vinstri, hægri). Nánar tiltekið, í þessum fjórum aðliggjandi stöðum verða engar nýjar slímklessur búnar til í stöðum sem þegar hafa einhverja aðra taflmenn eða eru utan marka skákborðsins.
- Slímklessurnar sem myndast við skiptingu hafa sömu skiptingareiginleika og engin takmörk eru á fjölda skiptinga.
Eftir að taflmenn eru færðir, ef þeir skarast við taflmenn óvinarins, virkjast dráp sem fjarlægir taflmenn óvinarins. Sigurskilyrði leiksins er að drepa allar Slímklessur óvinarins og tryggja að engir taflmenn óvinarins verði eftir á skákborðinu.
Meðan Xiao Biao spilaði leikinn komst hann að því að þótt óvinurinn geti ekki hreyft taflmenn sína, þá er samt erfitt fyrir okkar hlið að drepa Slímklessurnar hreinlega, þar sem þær eru margar og skipta sér mjög hratt, sem leiðir oft til þess að fleiri slímklessur myndast og gerir Xiao Biao erfitt fyrir að ákvarða hvort sigur sé mögulegur í þessum leik. Hann hefur leitað til þín, sem ert fær í herkænsku og greiningu, í von um að þú getir hjálpað honum að ákvarða hvort til sé áætlun til að ná sigri innan $10^4$ leikja. Ef slík siguráætlun er til, vinsamlegast skrifið út aðgerðirnar fyrir hvert skref.
Inntak
Inntakið samanstendur af $10$ línum, þar sem hver lína inniheldur streng af lengd $9$, sem táknar stöðuna á skákborðinu. Stafurinn . táknar auða stöðu; stafurinn C táknar Hrókinn okkar; stafurinn M táknar Riddarann okkar; og stafurinn S táknar Slímklessu óvinarins.
Hver tegund stafs getur komið fyrir mörgum sinnum. Gögnin tryggja að það sé að minnsta kosti ein Slímklessa á skákborðinu og að minnsta kosti einn vinveittur taflmaður.
Úttak
Ef engin áætlun er til sem vinnur innan $10^4$ leikja:
- Vinsamlegast skrifið út eina línu með strengnum
WuJie.
Ef til er áætlun sem vinnur innan $10^4$ leikja:
- Fyrst skal skrifa út eina línu með strengnum
YouJie. - Næst skal skrifa út heiltölu $s$, sem táknar fjölda aðgerða.
- Síðan skal skrifa út $s$ línur, þar sem hver lína inniheldur fjórar heiltölur $a, b, c, d$, sem gefa til kynna að vinveitti taflmaðurinn sem nú er á $(a, b)$ sé færður í stöðu $(c, d)$. Nánar tiltekið, ef báðar stöðurnar $(a, b)$ og $(c, d)$ hafa þegar vinveitta taflmenn, telst þessi aðgerð vera Hamskipti, sem gefur til kynna að þessir tveir taflmenn víxli stöðum.
- Áætlunin þín verður að tryggja að eftir að öllum aðgerðum er lokið séu engar Slímklessur eftir á skákborðinu.
Ef til eru margar ólíkar gildar lausnir má skrifa út hverja sem er.
Lausnir sem uppfylla ekki sniðskröfur, fylgja ekki hreyfireglum taflmanna eða gefa til kynna að enginn taflmaður sé á stöðu $(a, b)$ verða taldar rangar.
Dæmi
Inntak 1
...CSC... ...CCCM.. ......... ......... ......... ......... ......... ......... ......... .........
Úttak 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
Inntak 2
SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSCSSSS
Úttak 2
WuJie
Athugasemd
Úttakið fyrir dæmi $1$ sýnir margar gildar aðgerðir og drepur að lokum allar slímklessurnar.
- Skref $1$ til $3$ sýna Hrókinn á $(1, 4)$ færast til vinstri, einn reit í einu, og lenda að lokum á $(1, 1)$.
- Skref $4$ sýnir Hamskipta-aðgerðina, sem víxlar Hróknum á $(1, 1)$ við Hrókinn á $(2, 4)$.
- Skref $5$ sýnir Hrókinn á $(2, 4)$ færast upp á $(1, 4)$.
- Síðasta skrefið sýnir Riddarann stökkva frá $(2, 7)$ á $(1, 5)$ til að drepa einu Slímklessuna. Þar sem engar gildar auðar stöður eru aðliggjandi Slímklessunni eftir þetta getur hún ekki skipt sér. Leikurinn er unninn.