#P9971. [THUPC 2024 初赛] 三步棋
[THUPC 2024 初赛] 三步棋
题目背景
昼短夜长冬至近。江冽漆黑,但见东云粉。窗外惺忪鸥鹭阵,室中香漫晨炊奋。
朝肄暮劳催彼盹。宵寂观书,灯烬方安寝。请替君劳分重任,逍遥共舞生辰顺。
题目描述
K 家里有一条不成文的规矩。如果家里只有 K 和 H 两个人,那么两个人会通过一种叫作“三步棋”的游戏来决定谁做饭。三步棋的规则与五子棋有一些相似之处。众所周知,五子棋是一种先连出五枚己方棋子者获胜的游戏。与五子棋相同的是,三步棋中双方也轮流在网格状的棋盘上摆放棋子,并根据是否连成指定的图案决定胜负。与五子棋不同的是:
-
三步棋不区分双方的棋子,即可以认为双方执同色棋子进行游戏;
-
在判定时,指定的图案不能旋转;
-
如果连成指定的图案时,棋盘上的棋子数量恰好为 的倍数,则连成指定的图案的一方获胜,否则判定该方负(即对方获胜)。
例如,如果指定的图案为
.o
oo
且当前盘面为
o..o.
o.o..
oo...
o.o..
o..o.
时,认为没有连成给定的折线形图案,其中 o
表示棋子,.
表示空格;但若接下来在第二行第二列放一枚棋子,则连成了给定的图案,对应的棋子使用 @
表示:
o..o.
o@o..
@@...
o.o..
o..o.
此时盘面上恰有 枚棋子,而 不是 的倍数,所以判定放这枚棋子的玩家,也即先手输掉本局。
在 K 家,为了节约时间,通常使用 的初始为空的棋盘进行三步棋。同时,每次也只会随机选择一个由不超过 枚棋子组成的四连通图案。显然三步棋不存在平局,所以 K 和 H 约定由输的一方负责做饭。K 想知道,如果自己和 H 都足够聪明,那么以选中的图案进行的三步棋游戏是否为先手必胜;因为如果她更容易赢,她就要偷偷地给自己的妹妹放水。
输入格式
输入文件包含多组数据。
输入的第一行包含一个正整数 ,表示数据组数。保证 。
对于每组数据,输入包含 行,每行包括一个长度为 且仅含 .
及 o
的字符串,表示指定的图案。保证每组数据中 o
至少出现一次,且所有 o
组成一个大小不超过 的四连通块。
输出格式
对于每组数据输出一行。如果输入的图案为先手必胜,则输出 Far
,否则输出 Away
。
3
.....
oo...
.....
.....
.....
.o...
.o...
.....
.....
.....
.....
.....
.....
.ooo.
.....
Far
Far
Away
提示
样例 #1 解释
该样例包含三组数据。
第一组数据输入的图案为 行 列的 oo
。显然,无论先手将棋子放在棋盘上的哪个位置,后手都只有两种策略:
-
和先手的棋子连成
oo
,此时棋盘上只有 枚棋子,故后手立即输掉游戏; -
不和先手的棋子连成
oo
,但是接下来轮到先手时,先手可以任意连成oo
,此时棋盘上恰有 枚棋子,故先手取胜。
无论是哪种策略,后手都无法取胜,故对于 oo
而言先手必胜。
第二组数据输入的图案为 行 列的图案,与 oo
同理,可知为先手必胜。
第三组数据输入的图案为 行 列的 ooo
,可以证明为先手必败。
子任务
保证 。对于每组数据,保证输入的 的由 .
和 o
组成的字符矩阵中至少含有一个 o
,且所有 o
组成一个大小不超过 的四连通块。
题目使用协议
来自 THUPC2024(2024年清华大学学生程序设计竞赛暨高校邀请赛)初赛。
以下『本仓库』皆指 THUPC2024 初赛 官方仓库(https://github.com/ckw20/thupc2024_pre_public)
-
任何单位或个人都可以免费使用或转载本仓库的题目;
-
任何单位或个人在使用本仓库题目时,应做到无偿、公开,严禁使用这些题目盈利或给这些题目添加特殊权限;
-
如果条件允许,请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法;否则,请附上本仓库的 github 地址。