P8069 [BalticOI 2002] L Game © Edward de Bono (Day2)

题目描述

L 棋是一种双人棋类游戏,在 $4 \times 4$ 的正方形棋盘上进行。 共有两种棋子: - L 形棋:大小为 $4$,双方各有一枚; - 中性棋:大小为 $1$,共两枚,中立。 任意时刻,棋盘上任意格子上方应至多有一枚棋子。 双方轮流操作。一次合法的操作是:先移动己方 L 形棋至一个合法的与当前位置不同的位置,再移动至多一枚中性棋。 无法进行合法操作者败。 ![](https://cdn.luogu.com.cn/upload/image_hosting/pmca33zr.png) 记标有网格的 L 形棋操作者为 A,标有斜线者为 B。 若处于上图三种局面之一且 A 先手,则能且仅能将己方 L 形棋移至另外两种局面。此后,A 可以将中性棋之一移至某空格子,或不移动中性棋。故 A 共有 $2 \times (6 + 6 + 1)$ 种操作方案。 若处于下图局面且 A 先手,则 A 由于无法移动其 L 形棋而败,B 胜。 ![](https://cdn.luogu.com.cn/upload/image_hosting/9j9uia3u.png) 「妙棋」指:先手进行后存在必胜策略的操作。「败局」指:先手无论如何操作,后手都存在必胜策略的局面。「和棋」指:先手不存在妙棋且不为败局的局面。 尽管棋盘很小,但 L 棋存在超过 $18 \thinspace 000$ 种可能的局面;且在同一时刻先手可能存在多达 $195$ 种操作方案,但其中仅有一种妙棋。 对于给定局面,找到一步妙棋,或判定该局面为败局或和棋。若存在多种妙棋,输出任意一种即可。

输入格式

四行,每行四个字符,表示棋局。 - `#` 表示先手棋子所在位置; - `*` 表示后手棋子所在位置; - `x` 表示中性棋子所在位置; - `.` 表示空格子。

输出格式

- 若存在妙棋,则输出移动后的局面,格式同输入格式。注意 `#` 依然表示操作前的先手,`*` 同理。 - 否则第一行一个字符串 `No winning move`。 - 若为和棋,则第二行输出一个字符串 `Draw`; - 若为败局,则第二行输出一个字符串 `Losing`。 注意:虽然 Special Judge 忽略行末回车与文末换行,但请不要输出多于 $64$ 个字符,否则会被判为 Wrong Answer。

说明/提示

#### 数据范围 保证给出局面合法。 #### 提示 [BalticOI](https://boi.cses.fi/contests.php) 2002 Day2 B. 你能在不存在妙棋的测试点得分,当且仅当你通过了至少一半存在妙棋的测试点。(注:原题面中为至少一个,但这里取原题解中说法即「一半」。) 由于自定义计分脚本参数配置,暂不支持 AC WA TLE MLE 外的评测状态显示。如果你得到了此外任何一种评测状态,你将得到 UKE。 Subtask #0 为样例;Subtask #1 为数据。