这题属于那种拍脑袋想出来的.刚开始准备写个简单实现扔上来做算法帖来着.
结果发现我能写出的解法所需的时间都是惨不忍睹题目如下:给定字典 D <d0....dn>
其中dn是长度不定英文单词输入整数w h输出一个w×h的字符矩阵m.
要求:
1.对于m中的每一行和每一列都由空格分隔的字符串集合S<s0..sn>组成.且S⊆D
2.空格占一个字符
3.如果无法生成则提示无法生成嗯...说白了就是填字游戏.本来想用类似生成九宫格的方法来做.
结果发现tm的还真没那么好弄...所以干脆发上来大家讨论算了.需要字典的...可以下载我做的这个:由莎士比亚全集+圣经简英版+圣经James钦定版生成.
结果发现我能写出的解法所需的时间都是惨不忍睹题目如下:给定字典 D <d0....dn>
其中dn是长度不定英文单词输入整数w h输出一个w×h的字符矩阵m.
要求:
1.对于m中的每一行和每一列都由空格分隔的字符串集合S<s0..sn>组成.且S⊆D
2.空格占一个字符
3.如果无法生成则提示无法生成嗯...说白了就是填字游戏.本来想用类似生成九宫格的方法来做.
结果发现tm的还真没那么好弄...所以干脆发上来大家讨论算了.需要字典的...可以下载我做的这个:由莎士比亚全集+圣经简英版+圣经James钦定版生成.
其中每行每列中的单词都属于一个已知的字典D.
w×h和n的关系呢?
脑子一下子没转过弯了,感觉是不是有什么概念被我忽略了。
西瓜酱你不是没转过弯是酒喝多了吧
既然有词,肯定就有了词典.所有的词都是来自词典D
加上了更严格的限制:
1.不能有除单个字母外不成词的文本块.(原本是单个字母也不行的,后来考虑发现似乎这样要单是
弄出能符合要求的词典就头大)2.横向的单词之间不能有一个以上的空格.单个字母除外(放宽单个字母的限制原因同上)比如词典里有(但不限于)这些词:first
shall
gave
good
which
around
clean
little
there
would
from
five
after
please输入w=10,h=9
可以构造出一个10×9的方阵:■■f■s■gave
which■o■■■
■■r■around
c■s■l■d■■■
little■■w■
e■■h■■from
after■i■u■
n■■r■■v■l■
■please■d■
===========
给定集合 L = { a,b,c,...,z } (26个小写英文字母,当然用大写的也可以)
给定集合 L' = L 与 { 空格 } 的并集
给定集合 D = { d | 字符串d,对于任意字符l 属于d 有 l 属于 L }
对于自然数 w,h
构造 w*h 的矩阵 M ( m(x,y)表示M中第x行第y列的元素 )
m(1,1) m(1,2) .... m(1,h)
m(2,1) m(2,2) .... m(2,h)
.........................
m(w,1) m(w,2) .... m(w,h)要求M满足
C1 对于 M中的任意元素m 有 m 属于 L'
C2 任意自然数 t <= w,行集合 S = {m(t,1),m(t,2),...,m(t,h) }, f(S)包含于 D与L'的并集
C3 任意自然数 t <= h,列集合 S = {m(1,t),m(2,t),...,m(w,t) }, f(S)包含于 D与L'的并集函数f用于找出行/列中空格分隔的单词集合
c#:
Func<char[], string[]> f =
S => (new string(S)).Split(" ").Where(s => s.Trim().Length > 0).ToArray()仍有疑问,是否要求满足:
D1 对于任意d属于D, M中存在行集合/列集合S,使 d属于f(S)
D2 对于任意d属于D, M中不存在行集合/列集合 S1,S2 (S1不等于S2) 使 d属于f(S1) 且 d属于f(S2)==============
我觉得要满足D1条件的话无比艰难.....
难道要用穷举。
不允许单字符构造字典的得累死...那个puzzle是网上找的.据说还是"入门"级的....算了...过两天换个题来玩玩.