網(wǎng)上找的一些綜合材料專題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 剛剛學會如何拼圖。她現(xiàn)在開始玩 15 塊的小拼圖了。同時，他也在玩同樣的拼圖。為了是變得一些，他把

9、所有的拼圖塊翻轉(zhuǎn)過來使得他不能看到拼塊上的圖畫?，F(xiàn)在他在尋找這樣的拼圖的解答。一般來說，解答應該是存在的，但是他不敢肯定 Barborka 沒有換掉一部分拼塊。寫一個程序讀入一系列的拼塊并且?guī)退袛嗍欠窨梢园堰@些拼塊拼入一個給出長寬的矩形中。輸入格式：輸入包含很多塊，除了最后一塊之外，每塊都描述了一個拼圖問題。每塊的第一行包含由空格分隔的正整數(shù)n 和m，0 n, m = 6。n 和m 分別表示拼圖的行數(shù)和列數(shù)。這一塊的下面n * m 行是拼快的描述。每個拼塊是 3cm 寬 4cm 高的四邊中間可能有突起或凹陷的矩形塊。一個拼塊每一條邊都是下列情況之一：1. 平的-這樣的邊只能在最終圖形的邊上2

10、. 中間有突起3. 中間有凹陷像通常的拼圖一樣，兩條邊能拼在一起當且僅當其中一個有突起而另一個有凹陷。用F 表示平邊，O 表示突邊且I 表示凹邊。每個拼塊的四邊按上、右、下、左的順序依次給出。為了簡化問題，拼塊不能被旋轉(zhuǎn)。每塊結(jié)束后有一空行，最后一塊是兩個由空格隔開的 0。輸出格式：對每塊輸出一行。輸出 YES 如果輸入的拼圖問題有解，否則輸出 NO。最后一塊沒有對應的輸出。樣例輸入：3 5FOOF FOOI FOOI FOOI FFOI IOOF IOOI IOOI IOOI IFOI IOFF IOFI IOFI IOFI IFFI 0 0樣例輸出：YES理由：此題雖然數(shù)據(jù)規(guī)模很小，搜索完全可以解決。但拼塊總共不會超過 81 種且不能旋 轉(zhuǎn)，問題的數(shù)學模型并不復雜，而且四個角上的拼塊顯然是可以直接“構(gòu)造”出來的，所以我感覺可能有多項式級的算法直接判定解是否存在。在 zju 上有很多人的程序在 0.03 秒內(nèi)通過，這一點也多少為想法提供了:)，所以，即使不能找到多項式級的算法，至少也能找到很強的