Universal Cup Judging System

Universal Cup

Limite de temps : 1.0 s Limite de mémoire : 256 MB Points totaux : 100 Hackable ✓
Statistiques

problem_15427_1.png

喺一個 $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)$ 去食掉唯一嘅「史萊姆」。由於喺呢步之後,嗰隻「史萊姆」相鄰嘅位置冇可用嘅空位,所以佢唔能夠分裂。遊戲獲勝。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.