【正文】 中的點能直接相連的點，加入集合T，然后將T中所有元素加入到集合S中 (5)若B在集合S中，則A，B可以相連。）：//判斷圖片A與圖片B能否經(jīng)過不多于2個轉(zhuǎn)角的路徑相連的算法boolSet picture S 。//已經(jīng)搜索到的點的集合，集合S中每個元素與A都可以通過不多于個轉(zhuǎn)角的路徑連通 將A加入到S中int amp。{ { } crossNum ++ 。} return return}廣度優(yōu)先搜索算法，本質(zhì)上是一種建立搜索樹然后剪枝的策略。首先在圖形1所在位置向四個方向進行直線查找，如果在某一方向上找到圖形2則結(jié)束。如果仍未找到圖形2則再次記錄下查找過程中沿途記錄下來的空白格子（要去掉已經(jīng)走過的空白格子），仍然在3個方向上進行搜索。這個算法很直觀，就是在有限的轉(zhuǎn)彎次數(shù)內(nèi)不斷構(gòu)建出更大的路徑網(wǎng)絡(luò)，看看能否“覆蓋”到被連接的圖形，但還可以進一步提高效率，下面進行討論。由于題目要求最短路徑不能超過3個彎，并且我們知道：“直線路徑長度≤帶有一個彎的路徑長度≤帶有兩個彎的路徑長度”，所以下面我們將分三種情況進行討論。這一點我們可以通過他們的位置信息直接得到，例如圖形1的位置是[2,2]，圖形2的位置是[4,5]，很顯然二者不會在一條直線上，所以直接跳過這一步。例如，如果圖形2在[5,2]的話，我們可以斷定二者在同一直線上，但我們還需要檢查在二者的直線路徑上是否還有其他圖形存在。00110000，注意其中的兩個1是用來測試在圖2的第二列上是否有非空的格子。這一過程的時間復雜度為O(1)。從圖中我們可以清楚地看到，這樣的路徑只有兩條，他們組成了一個矩形，圖215中藍色的矩形就是兩條路徑的組合而成。這一步的時間復雜度也是O(1)。雖然左右兩組數(shù)據(jù)結(jié)構(gòu)的內(nèi)容是一樣的，但是其組織方式有所不同：左邊的二進制位是按列組織的，即一列的二進制位保存在一個int或者long型的變量中，多出來的位用0填滿；右邊的結(jié)構(gòu)是按行組織的，其他與左邊結(jié)構(gòu)類似。圖215第三步，查找兩個圖形間是否存在轉(zhuǎn)彎三次的路徑。如果沒找到所需路徑，則需要再次擴大搜索范圍。對于獲得的路徑上的3條線段，我們只需用第一步所提到的方法來查找是否存在障礙即可，若3條線段都沒有障礙則返回該路徑作為最短路徑；否則繼續(xù)向兩個方向擴展搜索范圍直到搜索范圍到達格子的邊界，若仍未找到則認為兩個圖形間沒有符合條件的最短路徑。(1)是否可以通過維護任意兩個格子之間的最短路徑來實現(xiàn)快速搜索。粗略想來，由于用戶每次只能消除一對圖形，即只會用到一個最短路徑，但由于實現(xiàn)并不知道用戶會選擇哪一對圖形，所以需要事先計算出所有可能的最短路徑并保存起來。其缺點很明顯就是每次消去圖形動作之后重新計算所有可能的最短路徑所需要消耗的時間；而該方法的優(yōu)點則是可以很快地判斷兩個相同圖形之間是否存在滿足條件的最短路徑。但這種情況是比較少的，因為在整個游戲中用戶主要是會用眼睛“找”而不是頻繁的用鼠標去“試”?？偨Y(jié)：考慮到第一種編程思路清晰明了，框架層次分明，能夠?qū)⑴袛嗟姆N類全部概括，每一個分支的實現(xiàn)都比較容易，所以對于初次實現(xiàn)連連看的我來說是一條捷徑，因此我選擇了分類判斷（分類法一）的方法來實現(xiàn)連連看的消除算法。下面簡單介紹下VB、C++、Java、Qt各自的特點：全稱Visual Basic，它是以Basic語言作為其基本語言的一種可視化編程工具。++的特點C/C++的哲學就不一樣了，同一份程序代碼，只要在該平臺重新Compile成該平臺的執(zhí)行檔，就能在該平臺執(zhí)行，若文字模式下的程序，的確可以跨平臺，程序完全不需修改，但GUI盛行以后，由于各GUI的Library都不一樣且沒有標準，所以GUI程序并沒辦法跨平臺Compile，因為各平臺都有專屬的 Library。除了GUI Library需要統(tǒng)一外，還得看該Library設(shè)計的好不好才行，若在Windows平臺，Borland的C++ Builder使用Delphi的VCL Library，Microsoft的Visual C++ Framework。再來看Microsoft的Visual C++，MFC用的是完整的ANSI C++語言，所以語言部分不是問題，但若你看過用MFC寫的程序，你一定會驚訝為什么這么復雜，程序代碼非常冗長不好看，且MFC是有名的難學，若 Visual C++ Framrwork，則無法使用ANSI C++，++/CLI，相信這點很多人就有意見了， Framework由于設(shè)計的不錯，所以寫出來的程序相當精簡漂亮，感覺和C++ Builder差不多，不過無論是C++ Builder或Visual C++開發(fā)的GUI，所開發(fā)出來的程序都無法跨平臺，當然也無法跨平臺Compile。 java能夠支持分布式，分布式開發(fā)可以說是現(xiàn)在大型企業(yè)級開發(fā)最重要的部分，通過rmi、ejb（本質(zhì)還是通過rmi實現(xiàn)）、webservice等方式實現(xiàn)不同系統(tǒng)、不同節(jié)點之間數(shù)據(jù)交互。 java語言在一定程度上能夠稱為動態(tài)語言，由于反射機制，讓java能夠在運行時再獲取相應(yīng)類型信息，大大減少開發(fā)的代碼量的同時，能夠提供更通用的程序。目前Qt已經(jīng)到第四個版本，GUI部分算支持的相當完整，且支持數(shù)據(jù)庫、XML、Multi Thread、Socket等方面的programming。Qt無疑是GUI終極解決方案，有強力的ANSI C/C++語言背書，又有單一的GUI Library，且精簡漂亮，又能Compile成各平臺的原生執(zhí)行檔，幾乎是最完美的解決方案了。 開發(fā)平臺分析：控件，框架和工具控件控件部分包括環(huán)境控件，主窗口控件，標準對話框, 基本的GUI控件，擴展GUI控件，GUI組織控件，以及幫助系統(tǒng)控件。例如QTranslator, Qapplication。標準對話框類是為打開/關(guān)閉文件，選擇顏色等預(yù)先設(shè)計的標準對話框，如QColorDialog, QFileDialog。擴展的控件包括樹狀視圖、進度條等, 如QListView。幫助系統(tǒng)控件是為應(yīng)用程序提供在線幫助的類,QStatusBar,QToolTip。對象模型是框架的基礎(chǔ)，如QObject。繪圖類控制繪圖, 如QBrush?？丶庥^類控制控件的外觀如顏色、字體等。工具工具部分包括時間日期和鏈表樹等數(shù)據(jù)結(jié)構(gòu),它們和GUI無關(guān)。圖形處理工具控制圖像的編碼/解碼算法。I/O控制工具處理I/O的一些類，如QFile。另外還有其他雜類如Qsignal, QIconSet等。如果需要實現(xiàn)對象間的通訊，只需要把一個對象的信號和另外一個對象的槽使用連接(connect)起來。信號—槽機制是Qt的一個中心特征并且也是它與其它圖形工具包的最不相同的部分。如圖216圖213在圖形用戶界面編程中，經(jīng)常希望一個窗口部件的一個變化被通知給另一個窗口部件。例如，如果正在解析一個XML文件，當遇到一個新的標簽時，也許要通知列表視圖正在用來表達XML文件的結(jié)構(gòu)?；卣{(diào)是指一個函數(shù)的指針，所以如果希望一個處理函數(shù)通知一些事件，可以把另一個函數(shù)(回調(diào))的指針傳遞給處理函數(shù)，處理函數(shù)在適當?shù)臅r候調(diào)用回調(diào)函數(shù)。在Qt中有一種可以替代回調(diào)的技術(shù)：使用信號和槽。Qt的窗口部件有很多預(yù)定義的信號，但是總是可以通過繼承來加入自己定義的信號。Qt的窗口部件有很多預(yù)定義的槽，通常也可以加入自己的槽，這樣就可以處理感興趣的信號了。實際上一個槽的簽名可以比它接收的信號的簽名少，因為它可以忽略額外的簽名。信號和槽是寬松地聯(lián)系在一起的：一個發(fā)射信號的類不用知道哪個槽要接收這個信號。信號和槽可以使用任何數(shù)量、任何類型的參數(shù)。從QObject類或者它的一個子類(比如QWidget類)繼承的所有類都可以包含信號槽。對象在發(fā)射信號時，無須知道有沒有槽接收它所發(fā)射的信號，而槽是正常的成員函數(shù)，一個槽不知道它是否被任何信號連接，這就是信息封裝，這種封裝確保了對象可以用作一個軟件組件。在信號—槽機制實現(xiàn)的過程中，可以把許多信號和單一槽相連，也可以把一個信號和許多槽相連。(這時，只要第一個信號被發(fā)射時，第二個信號立刻就被發(fā)射)?？偨Y(jié)：介于qt強大的類庫和完善的通信機制，為連連看的設(shè)計提供了良好的平臺環(huán)境，便于程序的設(shè)計與實現(xiàn)，故使用QT平臺。本系統(tǒng)的硬件開發(fā)環(huán)境是HP筆記本6450b：由于用戶對UI比較敏感，一般情況下，用戶對程序的第一印象就是來自于UI的展示，無論游戲的邏輯和功能再怎么強大，如果你的UI設(shè)計的粗糙，晦澀，讓人無法賞心悅目的話，這就是一個失敗的程序，用戶的體驗立即下降，針對游戲來說更是看中UI的設(shè)計，游戲的成功與否，一大半來自于界面，為了實現(xiàn)簡潔的UI，我選擇了藍色為主色調(diào)，看起來賞心悅目，心曠神怡。：一款經(jīng)典的游戲總是少不了音樂的配合，游戲和音樂總像是天生的一對，形影不離，美妙的音樂能夠激發(fā)玩家的游戲斗志和激情，因此音樂的配合就必不可少了，當玩家打開程序時候，悠揚的歌曲就呼之欲出，像一陣清風徐徐而來，不驚波瀾，立即把玩家?guī)脒B連看的游戲世界，當玩家點擊開始游戲，正式開始游戲的時候，點擊圖片會有提示音，當成功消除一對圖片的時候，會有相應(yīng)的提示音播放。尤其是在時間即將耗盡的時候，這種感覺更是突出，滿足了玩家的游戲持續(xù)性的需求。當然為了防止玩家偷懶，提示的次數(shù)也是有限的。、難度調(diào)節(jié)的需求：得分記錄、難度調(diào)節(jié)這是游戲的基本功能，得分記錄可以通過數(shù)據(jù)的方式記載玩家的游戲進度，不同玩家之間通過得分競爭頭名，提高玩家的積極性，難度可以避免一款游戲競爭力單一，玩家通過游戲太隨意，設(shè)置難度功能可以提高游戲的刺激性，激勵玩家。當玩家點擊一對可以消除的圖片時，能夠立刻播放消除音樂，并且能夠迅速的將圖片消除?？煽啃孕枨蠖康刂付ㄏ到y(tǒng)的可靠性。3. 游戲概要設(shè)計 任務(wù)概述 目標設(shè)計軟件的結(jié)構(gòu)，包括組成模塊，模塊的層次結(jié)構(gòu)，模塊的調(diào)用關(guān)系，每個模塊的功能等等。由于本程序沒有涉及到數(shù)據(jù)庫，所以這一塊就省略了。 總體設(shè)計 處理流程游戲流程描述：當玩家打開游戲時，主界面上有菜單欄兩枚，一個是游戲，另一個是幫助，游戲中包含三個菜單項，開始游戲，重新開始，退出，開始游戲是游戲的入口，當玩家點擊開始游戲之后，就可以正常進入游戲，在游戲過程中可以選擇重新開始，游戲便進入全新載入的模式；正常進入游戲時，游戲播放背景音樂，時間進度條提示游戲剩余時間，玩家可以點擊消除圖片，同樣在點擊圖片時有點擊音樂播放，在游戲結(jié)束后提示游戲勝負，提示過后，等待玩家再次開始游戲；游戲過程中，當玩家需要提示的時候，可以點擊提示按鈕，程序會用背景色提示玩家消除圖片，玩家點擊后可以消除。如圖31圖31 系統(tǒng)結(jié)構(gòu)圖對應(yīng)于需求分析，可以把程序分成四個模塊：游戲界面的設(shè)計，圖片初始化的生成，圖片路徑的判斷，背景音樂模塊，如圖32圖32 游戲界面模塊設(shè)計本程序的界面上的控件比較少，界面的布局相對來說也比較容易，主要是按鈕、菜單欄、提示標簽、進度條的實現(xiàn)，還有就是背景顏色的選擇。右側(cè)是一些游戲中用到的兩個按鈕，提示和重排。綜上，界面大致分為三塊，菜單欄、提示欄（包括特殊按鈕）、游戲點擊中心。 圖片的隨機生成首先游戲中心是由10*10的按鈕構(gòu)成的，要想在按鈕中顯示圖片同時還便于圖片在系統(tǒng)中的使用，這里通過數(shù)字和圖片綁定的方式，實現(xiàn)圖片在按鈕上的排布，圖片的加載需要url，我們通過提前將圖片編號（125），然后將圖片存放在同一路徑下，通過一個統(tǒng)一的字符串前綴實現(xiàn)圖片的統(tǒng)一加載，而在統(tǒng)一字符串中只含一個整形變量，圖片的標號和變量匹配，將圖片和變量相綁定，這樣就簡化了圖片的使用。這樣容量為100的數(shù)組可以存放4組圖片，共計2對，這樣前期的按序存放圖片就完成了。隨機函數(shù)可以很好的解決這個問題，首先應(yīng)用隨機函數(shù)產(chǎn)生一個下標在數(shù)組容量范圍內(nèi)的整形數(shù)字（0100），同時遍歷整個數(shù)組，將隨機下標對應(yīng)的值和遍歷下標對應(yīng)的值相互交換，當數(shù)組遍歷完畢，那么整個數(shù)組中的值已經(jīng)打亂，實現(xiàn)了亂序、隨機性。根據(jù)轉(zhuǎn)角數(shù)不得超過2個的規(guī)則，我們可以分為轉(zhuǎn)角數(shù)分別為0個、1個、2個這三種情況分別討論。（紅色塊為欲消除塊），如圖33圖33一個轉(zhuǎn)角連通：其實相當于兩個圖片劃出一個矩形，這兩個圖片是一對對角頂點，另外兩個頂點如果可以同時和這兩個棋子直連，那就說明可以一折連通。這樣就將問題轉(zhuǎn)化為了0個轉(zhuǎn)角和1個轉(zhuǎn)角的情況，0個轉(zhuǎn)角可以直接相連，1個轉(zhuǎn)角可以轉(zhuǎn)化為以C點和B點為對頂角的矩形中尋找另外兩個對頂角之一，看能否分別和B、C相直連。判斷是否經(jīng)兩個轉(zhuǎn)角連通的算法需要做兩個方向上的掃描：水平掃描和垂直掃描。為了判斷A，B能否通過2個轉(zhuǎn)角連通，則從A開始在水平方向上向左右掃描，并判斷經(jīng)過的點能否與B點經(jīng)過1個轉(zhuǎn)角連通。（紅色塊為欲消除塊，黑色代表其他阻攔塊，黃色c代表折點,綠色代表折線），如圖35圖35垂直掃描。顯然C點能與B點經(jīng)1個轉(zhuǎn)角連通，故A，B能經(jīng)2個轉(zhuǎn)角連通（紅色塊為欲消除塊，黑色代表其他阻攔塊，黃色c代表折點,綠色代表折線）,如圖36圖36這里運用的就是分類判斷的方法涵蓋全部的路徑可能，事實證明該算法正確無誤。音效的設(shè)置采用Qt中支持的Phonon多媒體框架，可以直接采用Phonon類的MediaObject方法來創(chuàng)建聲音對象，然后使用該類的createPlayer()方法來設(shè)置對應(yīng)的音樂文件，成功后就可以直接使用play來播放了?！?. 詳細設(shè)計 視圖層設(shè)計 界面效果圖，如圖41圖41 思路由于QT在圖形方面處理比較強大，主界面的設(shè)計可以用QT設(shè)計器自帶的ui設(shè)計界面來實現(xiàn)，使用ui設(shè)計界面最大的優(yōu)勢是減少代碼的編寫量，程序員可以將大部分的精力用于邏輯算法的設(shè)計，不必考慮界面的布局。下述代碼是圖片存放的實現(xiàn)。 int i,j = 0。 for (i = 0。 i += 2) {