任意大小网格内最优4字放置

Question

问题陈述:

给定四个单词,将它们放在amxn正方形网格中,使得网格区域尽可能小.

单词必须在网格内从左到右,从上到下运行.字母可能重叠,但不能形成其他字.所有单词都必须在一个巨链中相互链接.

可以用4个单词"一,二,三和四"形成的示例网格.请注意,最后一个网格是最优化的.

我正在尝试学习python,我认为这将是一个很好的应用程序,以切断我的牙齿.

任何想法如何构建我的数据和算法来解决这样的问题？我不是在寻找一个直接的答案,但有些提示如下:

使用此库,此类或此数据结构.或者通过可用空间这样迭代.

Answer 1

考虑一下您需要的最大网格尺寸是多少？如果单词是one, two, three, four，那么最大尺寸的网格将是

12 x 12。这是网格的大小，其中每个单词首尾相连，共享前一个单词的最后一个字母。

现在我们有空间了。你如何将这些词放入空格中？尝试考虑一种暴力方法。这会带来什么后果？

尝试迭代所有可能的模式组合。每个单词可以有 24 种方式放置，共有 4 个单词，因此您有大约 500,000 种组合，这对于现代计算机来说并不多。查看哪些模式实际上满足标准（字母匹配等）。

一旦你有了一个蛮力方法，你如何改进它呢？

就数据结构而言，您实际上只需要一个可以存储字符的网格。您可以使用嵌套列表结构、numpy 数组、pandas 或很多其他东西。首先尝试简单地解决问题，然后再细化。