这样的问题是在我的大学里给我的,也许有人会有有趣的算法来解决这个问题。在 stackoverflow 上有几个解决方案,但没有一个是好的(因为它们正在循环所有可能性)。
问题:找到所有可能的组合,将给定的单词分配到给定的表格、网格(矩形,见下面的输入)中。应该没有空闲单元格,单词可以从左到右或从上到下定位。单词不能在一行(列)中逐个单词地定位。
输入:矩形区域,示例:
+-----+
| * |
| |
+-----+
或者
+-----+
| * |
| |
| *|
| * |
+-----+
然后输入不同的单词(下一个输入数据)来填充该网格,例如:
cdi
zobxzst
tdxic
r
sc
zro
and etc ...
数字最初是未知的,但输入到标准输入结束 - 活动 EOF。
输出:如果存在一种解决方案,则在填充网格中输出该可能的解决方案。如果没有解决方案或解决方案数量,则输出 0 或该确切数字。
例子:
(表格输入)
+-----+
| * |
| |
| *|
| * |
| * *|
| * |
| |
+-----+
然后的话cdi
zobxzst
tdxic
r
sc
zro
rgfvacd
oikf
df
x
c
r
xvf
ogish
za
sh
fc
hh
h
bfkh
(每个作为输入,但这里用空格分隔。)
输出(仅 1 个解决方案):
+-----+
|zro*h|
|ogish|
|bfkh*|
|xvf*r|
|za*c*|
|sc*df|
|tdxic|
+-----+
重要提示:输入的网格仅限于 16 个(!)单元格,字数少于 60 个。我写了一个算法来搜索所有可能的组合,但它对我不起作用,因为执行时间有限(10我猜是秒)并且这个问题无法用粗略的算法解决(例如,15 个网格上的 15 个和大约 60 个!可能或更多可能的排列,可以在普通 2GHz PC 上处理大约 1 天?)。
也许存在另一个独特的解决方案。也许这个问题比编程更数学化,也许可以使用一些左右组合而不是上下组合?或者也许是加权细胞?
PS 我有 3 周的时间来解决这个问题,如果没有,我可以在 3 周后在这里发布解决方案(好消息);)