最优4字词位置内任意大小的网格

Question

问题陈述：

鉴于四个字，把它们放置平方的m×n个网格内，使得网格的面积尽可能小。

单词必须从左到右，从上到下在网格中运行。字母可能会重叠，但无法形成其他字词。所有的单词都必须在一个巨大的链条中相互关联。

可以用4个单词“1,2,3,4”形成的网格示例。注意最后一个网格是最优化的。

我努力学习Python和我认为这将是一个很好的应用程序在砍我的牙齿。

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

使用此库，或此类或此数据结构。或者通过可用空间迭代。

Answer 1

想想你需要什么最大尺寸的网格？如果字是one，two，three，four，则最大大小网格将

12×12。这是其中每个字被放在端连接到网格的尺寸结束，分享上一个单词的最后一个字母。

现在我们有空间了。你如何适应空间中的文字？尝试考虑一个暴力方法。那会带来什么？

尝试遍历所有可能的模式组合。您可以将每个单词放在24个单词中，并且有4个单词，因此您有大约50万个组合，这对于现代计算机来说并不多。查看哪些模式实际上符合标准（字母匹配等）。

一旦你有一个暴力方法，你怎么可以改进它？

在数据结构方面，你真的只需要一个可以存储字符的网格。你可以使用一个嵌套的列表结构，一个numpy数组，熊猫，或者其他很多东西。试着简单地先解决问题，然后再细化。