2

在单词搜索中系统地尝试所有可能的展示位置是否合理？

网格通常具有 15*15 的尺寸（15 个单元格宽，15 个单元格高）并包含大约 15 个要放置的单词，每个单词可以放置在 8 个可能的方向上。所以一般来说，您似乎可以通过以下方式计算所有可能的展示位置：width*height*8_directions_to_place_word*word of words

所以对于这样的网格，我们似乎只需要尝试 15*15*8*15 = 27,000，这看起来一点也不差。我期待一个巨大的数字，所以要么网格大小和单词数量非常小，要么我的数学有问题。

4

1 回答 1

2

正式地说，假设这x是行y数和列数，您应该对每个可能的单词的每个可能方向的所有概率求和。

输入是：x, y, l（单词的平均长度），n（总单词）

所以你有了

  • 在水平方向上，每行的单词可以从0to开始x-l并向右或从 lx向左：2x(x-l)
  • 垂直词使用相同的方法：它们可以从0下到y-l下或从l上到y上。所以是2y(y-l)
  • 对于对角线单词，您应该考虑所有可能的起始位置x*y并减去l^2，因为不能使用该字段的矩形。和之前一样，你乘以 4，因为你有 4 个可能的方向：4*(x*y - l^2)。

然后将整个结果乘以包含的单词数：

total = n*(2*x*(x-l)+2*y*(y-l)+4*(x*y-l^2)
于 2010-04-08T15:43:07.950 回答