娱乐 每 日 算 法 挑 战 【第B期】

[Mr.K 018]

第11期哦！

话说感觉来的人越来越少了啊，是不是该考虑转型了呢？转型成啥样比较好呢……（这里要 @NianRuoshui）

今天这个题算法不难，大家都可以来思考一下算法，能给出伪代码就更好了。

不多说，上题：

1. 钢哥的填字游戏

 

题目背景：

    BIT ACM/ICPC集训队教练**钢老师（钢哥）最近非常喜欢玩一款叫做”疯狂填字”的游戏。在去长沙赛区比赛的路上，钢哥和大家欢乐地玩了一路填字游戏。

 

    给定一个10 * 10的格子，其中一些格子不能填字，剩下的格子可以填字。所谓填字游戏，是要将一些字填入这些格子里，使得这些格子里的字从左至右或者从上到下构成一个词语。所有可填的格子必须填满。

    知识渊博的钢哥在游戏一开局就联想到了一些候选词语。给定一个填字游戏，钢哥想知道，用他自己想到的词语是否能够过关。

 

输入：

    第一行，一个整数N，代表钢哥想到的词语数（N <= 24）(每个词最多用一次，但不一定要全都用上)

    相同长度的词至多出现三个。

    接下来N行，每行一个长度大于等于2小于等于10的字符串（均为大写字母），代表钢哥知道的词。

    接下来是一个10 * 10的矩阵，代表游戏的初始状态。* 代表不可填的格子，# 代表可以填的格子。

    （见样例）

 

输出：

    如果用这些词汇可以过关，请输出答案。如果有解，保证解唯一。如果不可以，请输出QAQ

 

题目作者：

    PQ

 

样例输入1：

7
ALGORITHM
BIT
ACMICPC
WORD
PUZZLE
MATH
DIRECT
****#*****
*#########
*#**#****#
*#**######
###******#
*#********
*######***
*#********
**********
**********

样例输出1：

****W*****
*ALGORITHM
*C**R****A
*M**DIRECT
BIT******H
*C********
*PUZZLE***
*C********
**********
**********

样例输入2：

7
ALGORITHM
BIT
ACMICPC
WORD
PUZZLE
MATH
DIRECT
****#*****
*########*
*#**#****#
*#**######
###******#
*#********
*######***
*#********
**********
**********

样例输出2：

QAQ

召唤阵：

@yhz012 @inuisanaa @ZERC @随性而为 @摸鱼奇才咖啡喵

[yhz012]

艹，感觉又到了我的本职工作了，某种意义上和扫雷或者数独差不多吧，准确来说离数独更近，扫雷比这个还会涉及到一些置信度问题以及一些局部的SAT问题快速求解

 

因为反正只有24个词，我先根据长度sort一下应该不亏

另外我姑且假设不存在连续的2个词排在一起，所以根据长度已经可以剪枝掉很大一部分情况了。而且算一下格子和字符串长度能不能对上，对不上根本不用试了，直接QAQ就好了

 

接下来就先从可选情况最少的开始试就好了吧，这是最基本的heuristic

可选情况举例来说

现在有3个5字母，1个6字母，2个7字母

那应该先试1个6字母的，然后再试7字母的，最后是5字母的

 

另外我还有一个会有用的heuristic来tie-break

对于相同的可能情况，比如2个4字母的，1个3字母的，优先选用和其他格子交叉多的，比如3字母的和另外2个交叉，而6字母的只和1个交叉，那么先填3字母的，接着再填6字母的

加入4字母的交叉分别是1个和2个，7字母的交叉分别是3个和1个，那优先把3个交叉的7字母空格丢进来，然后再试2交叉的4字母

 

（说白了就是优先选用可能性最少，且对其他限制最多的来试

 

填入之后，根据交叉，就可以搜索指定长度字符串内指定位置带指定字母这样的字符串了，如果没有，直接剪枝然后backtrack

 

如果剪枝剪秃了，那就QAQ吧，不然会得到搜索结果的

四月 21, 2020，由yhz012修改

[NianRuoshui]

填字游戏单独拿出来感觉也不错……今后还是偏向娱乐向一些？