
喺一個 $10$ 行 $9$ 列嘅棋盤上面,正喺度進行一局叫做「奇門象棋」嘅遊戲。雙方各有若干隻棋子,唔同嘅棋子有唔同嘅特性。我哋用座標 $(x, y)$ 表示棋盤上面第 $x$ 行第 $y$ 列嘅位置。
我方擁有若干隻「車」(Rook)同埋若干隻「馬」(Knight),以及技能「移形換位」(Shape-shifting)。呢兩種棋子嘅移動方式同埋呢個技能嘅描述如下:
- 假設「車」位於座標 $(a, b)$。如果佢喺一步操作入面移動到棋盤上面嘅座標 $(c, d)$,必須滿足以下條件:
- $(c, d)$ 處冇我方棋子。即係佢唔可以食我方棋子,亦唔可以同我方棋子重疊。
- $c = a$ 或者 $d = b$,但係 $(a, b) \neq (c, d)$。即係佢可以沿住佢所在嘅行或者列移動,但係唔可以留喺原地。
- $(a, b)$ 同 $(c, d)$ 之間唔可以有任何其他棋子。即係佢喺移動嗰陣唔可以跳過其他棋子。
- 假設「馬」位於座標 $(a, b)$。如果佢喺一步操作入面移動到棋盤上面嘅座標 $(c, d)$,必須滿足以下條件:
- $(c, d)$ 處冇我方棋子。即係佢唔可以食我方棋子,亦唔可以同我方棋子重疊。
- $\{|a - c|, |b - d|\} = \{1, 2\}$。呢度 $\{\dots\}$ 表示無序集合。呢個對應傳統象棋入面「日」字形(或者「L」形)嘅移動(注意,呢道題入面冇「蹩馬腳」嘅規則)。
- 移形換位:呢個可以作為一步操作,用嚟交換任意兩隻我方棋子嘅位置。使用次數冇限制。
敵方擁有若干隻「史萊姆」(Slime)。史萊姆唔識移動,但係有以下特性:
- 假設「史萊姆」位於座標 $(a, b)$。當佢被食掉並移出棋盤嗰陣,佢會即刻分裂,喺相鄰嘅四個位置(上、下、左、右)各生成一隻「史萊姆」。具體嚟講,喺呢四個相鄰位置入面,如果某個位置已經有任何其他棋子或者超出咗棋盤邊界,噉嗰個位置就唔會生成新嘅史萊姆。
- 分裂生成嘅「史萊姆」具有相同嘅分裂特性,而且分裂次數冇限制。
棋子移動之後,如果同敵方棋子重疊,就會觸發食子,將敵方棋子移出棋盤。遊戲嘅獲勝條件係食晒所有敵方「史萊姆」,確保棋盤上面冇留低任何敵方棋子。
玩緊遊戲嗰陣,小標發現雖然敵方唔可以移動佢哋嘅棋子,但係我方依然好難乾淨俐落噉消滅晒所有史萊姆,因為佢哋數量好多而且分裂效率極高,成日搞到生成更多史萊姆,令小標好難判斷呢局遊戲有冇可能贏。佢搵到擅長策略同分析嘅你,希望你可以幫佢判斷係咪存在一種喺 $10^4$ 步之內贏得勝利嘅策略。如果存在噉樣嘅獲勝策略,請輸出每一步嘅操作。
輸入格式
輸入包含 $10$ 行,每行包含一個長度為 $9$ 嘅字串,表示棋盤嘅局勢。其中字元 . 表示空位置;字元 C 表示我方嘅「車」;字元 M 表示我方嘅「馬」;字元 S 表示敵方嘅「史萊姆」。
每種字元可能會出現多次。數據保證棋盤上面至少有一隻「史萊姆」同埋至少有一隻我方棋子。
輸出格式
如果唔存在喺 $10^4$ 步之內獲勝嘅策略:
- 請單行輸出字串
WuJie。
如果存在喺 $10^4$ 步之內獲勝嘅策略:
- 首先,單行輸出字串
YouJie。 - 接落嚟,輸出一個整數 $s$,表示操作嘅步數。
- 然後輸出 $s$ 行,每行包含四個整數 $a, b, c, d$,表示將目前位於 $(a, b)$ 嘅我方棋子移動到位置 $(c, d)$。特別噉,如果位置 $(a, b)$ 同 $(c, d)$ 都已經有我方棋子,噉呢步操作會被視為「移形換位」,表示呢兩隻棋子交換位置。
- 你嘅策略必須確保喺所有操作完成之後,棋盤上面冇剩低任何「史萊姆」。
如果存在多種唔同嘅合法解,輸出其中任意一種就得。
唔符合格式要求、唔符合棋子移動規則、或者指定位置 $(a, b)$ 處冇我方棋子嘅解將會被視為錯誤。
樣例
輸入 1
...CSC... ...CCCM.. ......... ......... ......... ......... ......... ......... ......... .........
輸出 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
輸入 2
SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSCSSSS
輸出 2
WuJie
說明
樣例 $1$ 嘅輸出展示咗多種合法操作,並且最終食晒所有史萊姆。
- 第 $1$ 到 $3$ 步展示咗位於 $(1, 4)$ 嘅「車」向左移動,選擇每次移動一格,最終停喺 $(1, 1)$。
- 第 $4$ 步展示咗「移形換位」操作,將位於 $(1, 1)$ 嘅「車」同位於 $(2, 4)$ 嘅「車」交換位置。
- 第 $5$ 步展示咗位於 $(2, 4)$ 嘅「車」向上移動到 $(1, 4)$。
- 最後一步展示咗「馬」由 $(2, 7)$ 跳到 $(1, 5)$ 去食掉唯一嘅「史萊姆」。由於喺呢步之後,嗰隻「史萊姆」相鄰嘅位置冇可用嘅空位,所以佢唔能夠分裂。遊戲獲勝。