问题 4372 --Wordle游戏 Ⅱ

4372: Wordle游戏 Ⅱ

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

Wordle游戏是一款风靡全球的益智游戏,在一场Wordle游戏中,你共有6次机会来猜出一个完全随机的单词,这个单词的长度和游戏的级别相关,让我们以一场级别5的Worlde游戏为例:


在第一轮中,我们尝试了单词 power,其中:

① 字母 p,o,r 的提示为灰色,表示这三个字母不会出现在答案中;

② 字母 w,e 的提示为黄色,表示这两个字母会出现在答案中,但是不在当前的位置上;也就是说在答案中,字母 w 不会在位置 3 上出现,字母 e 不会在位置 4 上出现;


在第二轮中,我们尝试了单词 twine,其中:

① 字母 t 的提示为灰色,表示字母 t 不会出现在答案中;

② 字母 w,i,n的提示为黄色,表示这三个字母会出现在答案中,但是不在当前的位置上;也就是说在答案中,字母 w 不会在 位置 2 上出现,字母 i 不会在位置 3 上出现,字母 n 不会在位置 4 上出现;

③ 字母 e 的提示为绿色,表示字母 e 目前的摆放位置正确;也就是说答案的第 5 个字母是字母 e;


到目前为止,我们获取了如下信息:

① 字母 r,t,o,p 不会出现在答案中;

② 答案中包含字母 w,且不会出现在第 2 个位置或第 3 个位置上;

③ 答案中包含字母 i,且不会出现在第 3 个位置上;

④ 答案中包含字母 n,且不会出现在第 4 个位置上;

⑤ 答案的第 5 个字母一定是字母 e ;


让我们用下划线来表示不能确定的字母,那么答案只有可能是以下 7 个排列中的一个:

win_e
wn_ie
w_nie

in_we
i_nwe
ni_we
_inwe



我们现在适当简化一下这个游戏:设游戏的级别为n,且在游戏进行了若干轮之后,我们已经知道了组成答案的全部n个字母(分别标号为1~n)只是不知道它们各自的位置;并且我们知道了一些提示:某些位置上绝对不可能出现某些字母;能否请你编写一份代码,按照字典序输出满足这些条件的、所有可能的字母排列,帮助我们完成填字游戏?

输入

输入包含多行,第一行包含2个正整数n, k, 表示单词的长度和
限制的数量;
第二行包含n个字符,中间用空格隔开,表示已知的、构成单词的字符;
其中可能用多个"_"表示未知字母;
接下来k行,每行表示一条限制,格式形如:"x c", 其中x为[1, n]
之间的整数,c为输入字符中的一个、且不是"_"; 意为:字符c不可以出
现在单词的第x个位置上;

输出

输出所有可能的单词,每个一行

样例输入

5 12
d a g y u
1 d
5 d
1 a
3 a
4 a
5 a
3 g
1 y
2 y
3 y
4 y
2 u

样例输出

gaduy
gaudy
uadgy

提示

来源

[提交][状态]