网上找的一些综合材料专题hqm

1、题目来源：http已有算法：搜索者：候启明题目描述：/show_problem.?=1264PuzzleTime limit: 30 SecondsMemory limit: 32768KLittarborka has juststarted to learn how to solve a picture puzzle. She hasstarted wismall onecontaining 15 pie. Her daddy tries to solve the puzzletoo. To make it upside down so solution of thea littirder

2、for himself, he has turned all puzzlet he cannot sectures on the. Now he is looking for apuzzle. Normally the solution should exist but he is not surewhether Barborka has not replaced someof the puzzy pieof anothersimilar puzzle. Help him and write aprogram which reads a description of a set ofpuzzl

3、eand decides whether itissible to assembly th not.eo arectangle with given side lengths orInputThe inponsists of blocksof lines. Each block except the lastdescribes onen and m, 0 n, mpuzzle problem.= 6 separated byheone space.line of the block there areegersTheegers n, m indicate the number of rows

4、andcolumnshe puzzle respectively.The description of individual puzzleishe following n * m lines of theblock. Each piece is a rectangle 3 centimeterswide and 4 sides. For true (secentimeters high with each side of a puzzl cture):sible juts or cavitieshe middle of itsece just one of the followingsibil

5、ities is1.there is no jut oron the side, i.e., the side is flat - such the final picture when assembling the puzzle,sidescan be used only on edges of2. thereis onejuthemiddle of the side,3. thereis onehe middle of the side.As is other sidesusual, two has apiecanbe placed side by side only if one has

6、 a jut and theon corresponding sides. We will denote the flat sides by F,the by taskwith juts by O and the sides with cavities by I. Each piece is describedfour letters characterizing its top, right, bottom, and left side. To make theeasier thecan be used only as they are described i.e. they cannot

7、be turned.After each containingblock there is an empty line. The last block consists of just one line 0 0, i.e. two zeros separated by one space.OutputThe outpontains the lines corresponding to the blockshe input. A linecontains YES if the corresponding blockhe input describes a puzzlet can becorrec

8、tly assembled. Otherwise it contains NO. There is no line corresponding to the last null block of the input.he outputSleInput3 5FOOF FOOI FOOI FOOI FFOI IOOF IOOI IOOI IOOI IFOI IOFF IOFI IOFI IOFI IFFI 0 0SleOutputYES拼图时间限制：30 秒空间限制：32768K小 Barborka 刚刚学会如何拼图。她现在开始玩 15 块的小拼图了。同时，他也在玩同样的拼图。为了是变得一些，他把

9、所有的拼图块翻转过来使得他不能看到拼块上的图画。现在他在寻找这样的拼图的解答。一般来说，解答应该是存在的，但是他不敢肯定 Barborka 没有换掉一部分拼块。写一个程序读入一系列的拼块并且帮他判断是否可以把这些拼块拼入一个给出长宽的矩形中。输入格式：输入包含很多块，除了最后一块之外，每块都描述了一个拼图问题。每块的第一行包含由空格分隔的正整数n 和m，0 n, m = 6。n 和m 分别表示拼图的行数和列数。这一块的下面n * m 行是拼快的描述。每个拼块是 3cm 宽 4cm 高的四边中间可能有突起或凹陷的矩形块。一个拼块每一条边都是下列情况之一：1. 平的-这样的边只能在最终图形的边上2

10、. 中间有突起3. 中间有凹陷像通常的拼图一样，两条边能拼在一起当且仅当其中一个有突起而另一个有凹陷。用F 表示平边，O 表示突边且I 表示凹边。每个拼块的四边按上、右、下、左的顺序依次给出。为了简化问题，拼块不能被旋转。每块结束后有一空行，最后一块是两个由空格隔开的 0。输出格式：对每块输出一行。输出 YES 如果输入的拼图问题有解，否则输出 NO。最后一块没有对应的输出。样例输入：3 5FOOF FOOI FOOI FOOI FFOI IOOF IOOI IOOI IOOI IFOI IOFF IOFI IOFI IOFI IFFI 0 0样例输出：YES理由：此题虽然数据规模很小，搜索完全可以解决。但拼块总共不会超过 81 种且不能旋 转，问题的数学模型并不复杂，而且四个角上的拼块显然是可以直接“构造”出来的，所以我感觉可能有多项式级的算法直接判定解是否存在。在 zju 上有很多人的程序在 0.03 秒内通过，这一点也多少为想法提供了:)，所以，即使不能找到多项式级的算法，至少也能找到很强的