9

问题陈述:

给定四个单词,将它们放在正方形的 amxn 网格中,使网格的面积尽可能小。

单词必须在网格内从左到右,从上到下运行。字母可以重叠,但不能形成额外的单词。所有的词都必须在一个巨大的链条中相互连接。

可以用 4 个单词“一、二、三和四”组成的示例网格。请注意,最后一个网格是最优化的。

在此处输入图像描述

我正在尝试学习 python,我认为这将是一个很好的应用程序。

任何想法如何构建我的数据和算法来解决这样的问题?我不是在寻找一个直截了当的答案,而是一些提示,例如:

使用这个库,或者这个类,或者这个数据结构。或者像这样遍历可用空间。

4

1 回答 1

2

想想你需要的最大网格尺寸是多少?如果单词是one, two, three, four,那么最大尺寸网格将是

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

现在我们有了空间。你如何在空间中放置单词?尝试考虑一种蛮力方法。那会带来什么?

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

有了蛮力法,怎么炼?

在数据结构方面,你真的只需要一个可以存储字符的网格。您可以使用嵌套列表结构、numpy 数组、pandas 或许多其他东西。尝试先简单解决问题,然后再细化。

于 2013-06-26T15:40:09.893 回答