網(wǎng)上找的一些綜合材料專題hqm

1、題目來(lái)源：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拼圖時(shí)間限制：30 秒空間限制：32768K小 Barborka 剛剛學(xué)會(huì)如何拼圖。她現(xiàn)在開(kāi)始玩 15 塊的小拼圖了。同時(shí)，他也在玩同樣的拼圖。為了是變得一些，他把

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

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