算法与程序实践1（简单计算）(3)

思考题：

如果马路长度L的值极大，比如是40亿，以至于无法开设这么大的trees数组，本题该如何解决？

CS6：填词

（来源：poj.grids.cn 2801） 问题描述：

Alex 喜欢填词游戏。填词游戏是一个非常简单的游戏。填词游戏包括一个N *M 大小的矩形方格盘和P个单词。然后需要把每个方格中填上一个字母使得每个单词都能在方格盘上被找到。每个单词都能被找到要满足下面的条件：

每个方格都不能同时属于超过一个的单词。一个长为k的单词一定要占据k个方格。单词在方格盘中出现的方向只能是竖直的或者水平的（可以由竖直转向水平，反之亦然）。 你的任务是首先在方格盘上找到所有的单词，当然在棋盘上可能有些方格没有被单词占据。然后把这些没有用的方格找出来，把这些方格上的字母按照字典序组成一个“神秘单词”。

如果你还不了解规则，我们可以用一个例子来说明，比如在图1-2中寻找单词BEG和GEE。

E B G G E E E G E 正确

E B G G E E E G E 不正确，(2,2)中的字母E属于两个单词

E B G G E E E G E 不正确，(3,1)和(2,2)中的字母E不相邻

E B G G E E E G E 不正确，(2,2)中的字母E被用了两次

8

图1-2 填词游戏方格盘

输入：

输入的第一行包括三个整数N，M 和P (2 <= M, N <= 10, 0 <= P <=100) 。接下来的N 行，每行包括M个字符来表示方格盘。接下来P行给出需要在方格盘中找到的单词。

输入保证填词游戏至少有一组答案。输入中给出的字母都是大写字母。

输出要求

输出“神秘单词”，注意“神秘单词”中的字母要按照字典序给出。 输入样例

3 3 2 EBG GEE EGE BEG GEE 输出样例

EEG

解题思路

题目中给出的条件比较隐晦。输入中给出的字母都是大写字母——表明输出也只能是大写字母。输入保证填词游戏至少有一组答案——这说明我们不必寻找单词所在的位置，只要去掉这些单词所占用的字母就可以了。“神秘单词”中的字母要按照字典序给出——说明我们只要知道“神秘单词”中的字母组成就可以了，在字母组成确定的情况下，按字典序输出的方式只有一种。分析到这里我们发现这其实是个很简单的问题。给出一个字母的集合，从中去掉一些在给出单词中出现过的字母，将剩下的字母按字典序输出！

可以定义一个有26个元素的数组，分别记录在输入的矩形中，每个字母出现的次数，当读入单词时，将数组中对应到单词中的字母的元素值减一。处理完所有的单词后，将数组中的非0 的元素对应的字母依次输出，数组元素的值是几，就输出几次该字母。

CS7：装箱问题

（来源：poj.grids.cn 1017）

问题描述：

一个工厂制造的产品形状都是长方体，它们的高度都是h，长和宽都相等，一共有六个型号，他们的长宽分别为1*1, 2*2, 3*3, 4*4, 5*5, 6*6. 这些产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵，所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。 输入：

输入文件包括几行，每一行代表一个订单。每个订单里的一行包括六个整数，中间用

9