【正文】 觀，就是在有限的轉(zhuǎn)彎次數(shù)內(nèi)不斷構(gòu)建出更大的路徑網(wǎng)絡(luò)，看看能否“覆蓋”到被連接的圖形，但還可以進(jìn)一步提高效率，下面進(jìn)行討論。圖213以圖214為例，我們的目標(biāo)是找到圖形1和圖形2之間的最短路徑，我們從圖形1出發(fā)進(jìn)行查找動(dòng)作。由于題目要求最短路徑不能超過3個(gè)彎，并且我們知道：“直線路徑長度≤帶有一個(gè)彎的路徑長度≤帶有兩個(gè)彎的路徑長度”，所以下面我們將分三種情況進(jìn)行討論。圖214首先，應(yīng)該判斷是否存在圖形1到圖形2之間的直線路徑。這一點(diǎn)我們可以通過他們的位置信息直接得到，例如圖形1的位置是[2,2]，圖形2的位置是[4,5]，很顯然二者不會(huì)在一條直線上，所以直接跳過這一步。但如果二者在一條直線上的話，還需要判斷他們之間是否有障礙物存在。例如，如果圖形2在[5,2]的話，我們可以斷定二者在同一直線上，但我們還需要檢查在二者的直線路徑上是否還有其他圖形存在。因?yàn)閮蓚€(gè)圖形同在第二列上，于是我們?nèi)D215左邊結(jié)構(gòu)的第二列變量C2（這里假設(shè)是一個(gè)8位的Byte變量），然后做val=C2amp。00110000，注意其中的兩個(gè)1是用來測試在圖2的第二列上是否有非空的格子。如果val=0則說明兩個(gè)圖形間存在直線路徑，否則說明二者之間不存在直線路徑。這一過程的時(shí)間復(fù)雜度為O(1)。第二步，查找二者之間是否存在轉(zhuǎn)彎一次的路徑。從圖中我們可以清楚地看到，這樣的路徑只有兩條，他們組成了一個(gè)矩形，圖215中藍(lán)色的矩形就是兩條路徑的組合而成。我們可以用上面的方法分別來測試這兩條路徑上是否有障礙存在，如果沒有障礙則作為最短路徑返回，否則就要進(jìn)行第三步。這一步的時(shí)間復(fù)雜度也是O(1)。為了加速程序運(yùn)行，這里還引入了圖215所示的兩個(gè)輔助數(shù)據(jù)結(jié)構(gòu)，其中每一個(gè)方塊中都帶有一個(gè)二進(jìn)制位，用來表示在該位置上的格子是否是空格子，0代表是空格子，1代表有圖形存在。雖然左右兩組數(shù)據(jù)結(jié)構(gòu)的內(nèi)容是一樣的，但是其組織方式有所不同：左邊的二進(jìn)制位是按列組織的，即一列的二進(jìn)制位保存在一個(gè)int或者long型的變量中，多出來的位用0填滿；右邊的結(jié)構(gòu)是按行組織的，其他與左邊結(jié)構(gòu)類似。這兩個(gè)結(jié)構(gòu)具體的功能后面用到的時(shí)候會(huì)詳細(xì)介紹。圖215第三步，查找兩個(gè)圖形間是否存在轉(zhuǎn)彎三次的路徑。首先我們用指定方法在藍(lán)色矩形內(nèi)部進(jìn)行路徑查找，但是限制只在“向右”和“向下”兩個(gè)方向上進(jìn)行操作。如果沒找到所需路徑，則需要再次擴(kuò)大搜索范圍。如圖214所示，在這一步我們需要把搜索方向在“向上”和“向左”兩個(gè)方向上擴(kuò)展，所獲得的路徑分別用紅色框和粉色框表示，這個(gè)動(dòng)作類似于把藍(lán)色框向上和向左拉伸。對(duì)于獲得的路徑上的3條線段，我們只需用第一步所提到的方法來查找是否存在障礙即可，若3條線段都沒有障礙則返回該路徑作為最短路徑；否則繼續(xù)向兩個(gè)方向擴(kuò)展搜索范圍直到搜索范圍到達(dá)格子的邊界，若仍未找到則認(rèn)為兩個(gè)圖形間沒有符合條件的最短路徑。可以看出，由于不需要對(duì)同時(shí)對(duì)4個(gè)方向上所有空閑格子進(jìn)行廣度優(yōu)先搜索操作，第三步的時(shí)間復(fù)雜度應(yīng)該低于書中所給出的算法。(1)是否可以通過維護(hù)任意兩個(gè)格子之間的最短路徑來實(shí)現(xiàn)快速搜索。(2)在每次消去兩個(gè)格子之后，自然更新要更新需要維護(hù)的數(shù)據(jù)，這樣的思路有哪些優(yōu)缺點(diǎn)，如何實(shí)現(xiàn)。粗略想來，由于用戶每次只能消除一對(duì)圖形，即只會(huì)用到一個(gè)最短路徑，但由于實(shí)現(xiàn)并不知道用戶會(huì)選擇哪一對(duì)圖形，所以需要事先計(jì)算出所有可能的最短路徑并保存起來。此外，采用這種方法的話似乎每次用戶消去一對(duì)相同圖像之后都需要重新計(jì)算出當(dāng)前所有可能被連接的相同圖形之間最短路徑，這是因?yàn)楫?dāng)某些圖像被消去之后可能會(huì)產(chǎn)生很多新路徑，而我們又不能確定這些空出來的格子到底能夠影響哪些路徑，所以就只好都重新計(jì)算一遍。其缺點(diǎn)很明顯就是每次消去圖形動(dòng)作之后重新計(jì)算所有可能的最短路徑所需要消耗的時(shí)間；而該方法的優(yōu)點(diǎn)則是可以很快地判斷兩個(gè)相同圖形之間是否存在滿足條件的最短路徑。如果用戶很厲害，每次都能選中可以消除的圖形對(duì)，那么用這種方法浪費(fèi)的時(shí)間就會(huì)相當(dāng)可觀，畢竟用戶未選中的其他可以連接的圖形對(duì)之間的最短路徑都被浪費(fèi)掉了；而如果用戶很差勁，每輪選擇的次數(shù)都遠(yuǎn)遠(yuǎn)大于當(dāng)前可能的連接數(shù)量時(shí)，該方法就會(huì)比書中正文提到的方法高效。但這種情況是比較少的，因?yàn)樵谡麄€(gè)游戲中用戶主要是會(huì)用眼睛“找”而不是頻繁的用鼠標(biāo)去“試”。所以總的來看，維護(hù)所有最短路徑的方法的效率相對(duì)比較低?？偨Y(jié)：考慮到第一種編程思路清晰明了，框架層次分明，能夠?qū)⑴袛嗟姆N類全部概括，每一個(gè)分支的實(shí)現(xiàn)都比較容易，所以對(duì)于初次實(shí)現(xiàn)連連看的我來說是一條捷徑，因此我選擇了分類判斷（分類法一）的方法來實(shí)現(xiàn)連連看的消除算法。 開發(fā)語言分析根據(jù)自己以前所學(xué)的關(guān)于C語言、C++、Java、以及Qt的相關(guān)知識(shí)，并通過網(wǎng)上查找相關(guān)資料，了解到 C、C++、VB、Delphi、C、Java等均可以游戲的設(shè)計(jì)。下面簡單介紹下VB、C++、Java、Qt各自的特點(diǎn)：全稱Visual Basic，它是以Basic語言作為其基本語言的一種可視化編程工具。在中國乃至全世界都能看到它的身影，它曾是在中國最為流行的編程工具，到現(xiàn)在還占據(jù)著非常重要的地位，對(duì)于它的好壞大家都有一定的了解，VB作為一種較早出現(xiàn)的開發(fā)程序以其容易學(xué)習(xí)，開發(fā)效率較高，具有完善的幫助系統(tǒng)等優(yōu)點(diǎn)曾影響了好幾代編程人員，但是由于VB不具備跨平臺(tái)這個(gè)特性，從而也決定了VB在未來的軟件開發(fā)中將會(huì)逐漸地退出其歷史舞臺(tái)；它對(duì)組件技術(shù)的支持是基于COM和ActiveX,對(duì)于組件技術(shù)不斷完善發(fā)展的今天，它也顯出了它的落后性；同時(shí)VB在進(jìn)行系統(tǒng)底層開發(fā)的時(shí)候也是相對(duì)復(fù)雜的，調(diào)用API函數(shù)需聲明，調(diào)用不方便，不能進(jìn)行DDK編程，不可能深入Ring0編程，不能嵌套匯編；而且面向?qū)ο蟮奶匦圆?；網(wǎng)絡(luò)功能和數(shù)據(jù)庫功能也沒有非常突出的表現(xiàn)，綜上所述，VB作為一種可視化的開發(fā)工具由于其本身的局限性，導(dǎo)致了它在未來軟件開發(fā)中逐步被其他工具所代替。++的特點(diǎn)C/C++的哲學(xué)就不一樣了，同一份程序代碼，只要在該平臺(tái)重新Compile成該平臺(tái)的執(zhí)行檔，就能在該平臺(tái)執(zhí)行，若文字模式下的程序，的確可以跨平臺(tái)，程序完全不需修改，但GUI盛行以后，由于各GUI的Library都不一樣且沒有標(biāo)準(zhǔn)，所以GUI程序并沒辦法跨平臺(tái)Compile，因?yàn)楦髌脚_(tái)都有專屬的 Library。但是C/C++優(yōu)勢就是執(zhí)行速度快，若能解決GUI Library的問題，則跨平臺(tái)即可解決。除了GUI Library需要統(tǒng)一外，還得看該Library設(shè)計(jì)的好不好才行，若在Windows平臺(tái)，Borland的C++ Builder使用Delphi的VCL Library，Microsoft的Visual C++ Framework。首先來看Borland的C++ Builder，它使用標(biāo)準(zhǔn)的ANSI C++語言開發(fā)，利用VCL寫出來的程序也算蠻漂亮的，執(zhí)行速度很快，比較麻煩的是C++ Builder當(dāng)初為了縮短上市時(shí)間，并沒有設(shè)計(jì)自己的Library，而是借用Delphi的Library，導(dǎo)致C++ Builder在Compile時(shí)，是先用Delphi的Compiler將VCL pile成object file后，再用C++ Builder將你寫的C++程序pile成object file，最后再用Linker將所有的object file link起來，由于這都是IDE在做，對(duì)程序設(shè)計(jì)師似乎影響不大，但VCL由于是Delphi的Library，所以若想深入研究VCL的source code時(shí)，則必須學(xué)Delphi的Pascal才行，否則看不懂VCL source code，這也是很多人對(duì)C++ Builder卻步的原因。再來看Microsoft的Visual C++，MFC用的是完整的ANSI C++語言，所以語言部分不是問題，但若你看過用MFC寫的程序，你一定會(huì)驚訝為什么這么復(fù)雜，程序代碼非常冗長不好看，且MFC是有名的難學(xué)，若 Visual C++ Framrwork，則無法使用ANSI C++，++/CLI，相信這點(diǎn)很多人就有意見了， Framework由于設(shè)計(jì)的不錯(cuò)，所以寫出來的程序相當(dāng)精簡漂亮，感覺和C++ Builder差不多，不過無論是C++ Builder或Visual C++開發(fā)的GUI，所開發(fā)出來的程序都無法跨平臺(tái)，當(dāng)然也無法跨平臺(tái)Compile。java是面向?qū)ο蟮木幊陶Z言，和其他面向?qū)ο缶幊陶Z言一樣，在java的世界里，萬物皆對(duì)象，面向?qū)ο缶幊痰暮锰幘褪悄軌蛟谡Z言級(jí)別模擬現(xiàn)實(shí)世界的場景，簡化開發(fā)。 java能夠支持分布式，分布式開發(fā)可以說是現(xiàn)在大型企業(yè)級(jí)開發(fā)最重要的部分，通過rmi、ejb（本質(zhì)還是通過rmi實(shí)現(xiàn)）、webservice等方式實(shí)現(xiàn)不同系統(tǒng)、不同節(jié)點(diǎn)之間數(shù)據(jù)交互。 java是體系結(jié)構(gòu)中立的，由于這種特點(diǎn)，讓很多其他的語言能夠運(yùn)行在jvm（java虛擬機(jī)）上，比如jruby、jython等語言（沒記錯(cuò)應(yīng)該有100多種語言），同時(shí)也讓他能夠在不同的平臺(tái)上運(yùn)行。 java語言在一定程度上能夠稱為動(dòng)態(tài)語言，由于反射機(jī)制，讓java能夠在運(yùn)行時(shí)再獲取相應(yīng)類型信息，大大減少開發(fā)的代碼量的同時(shí)，能夠提供更通用的程序。Qt擁有一個(gè)單一的Library，讓你開發(fā)各種不同平臺(tái)的程序，目前支持Windows、Linux、Mac、UNIX、Embedded Linux，就是它提供了一個(gè)Library讓你開發(fā)GUI程序，寫好之后，只要在各平臺(tái)重新Compile后，就可以在各平臺(tái)執(zhí)行，而且使用完整的ANSI C++語言，且不限Compiler，只要是C++的Compiler都可以，重要的是，該Library相當(dāng)漂亮，寫出來的程序很像C++ Framework的那樣精簡，不會(huì)向MFC那樣復(fù)雜。目前Qt已經(jīng)到第四個(gè)版本，GUI部分算支持的相當(dāng)完整，且支持?jǐn)?shù)據(jù)庫、XML、Multi Thread、Socket等方面的programming。若以后臺(tái)角度來說，無論后端是什么數(shù)據(jù)庫，只要透過相同的Interface，不同數(shù)據(jù)庫的Class來實(shí)做這個(gè)Interface，前端GUI的程序?qū)懛ㄍ耆挥酶淖?，同理，面?duì)不同的OS，理論上只要透過相同的Interface，不同OS的Class各自實(shí)做這個(gè)Interface，前端GUI的程序也完全不用改變，最后只要靠Compiler將程序pile成各平臺(tái)的原生程序即可，這樣即可保證其執(zhí)行速度，不用再靠Virtual Machine。Qt無疑是GUI終極解決方案，有強(qiáng)力的ANSI C/C++語言背書，又有單一的GUI Library，且精簡漂亮，又能Compile成各平臺(tái)的原生執(zhí)行檔，幾乎是最完美的解決方案了?？偨Y(jié)：經(jīng)過以上比較后，考慮到Qt的眾多良好特性，尤其是其跨平臺(tái)性，加上自己在基地學(xué)習(xí)過Qt，為了能夠更進(jìn)一步掌握Qt編程，因此決定使用Qt開發(fā)連連看游戲。 開發(fā)平臺(tái)分析：控件，框架和工具控件控件部分包括環(huán)境控件，主窗口控件，標(biāo)準(zhǔn)對(duì)話框, 基本的GUI控件，擴(kuò)展GUI控件，GUI組織控件，以及幫助系統(tǒng)控件。環(huán)境控件為應(yīng)用程序提供全局服務(wù)的類，包括系統(tǒng)設(shè)定、國際化等。例如QTranslator, Qapplication。主窗口類為應(yīng)用程序提供界面框架，可以在上面添加菜單、工具條等，為應(yīng)用程序提供集裝箱的功能，如QMainWindow。標(biāo)準(zhǔn)對(duì)話框類是為打開/關(guān)閉文件，選擇顏色等預(yù)先設(shè)計(jì)的標(biāo)準(zhǔn)對(duì)話框，如QColorDialog, QFileDialog?；究丶ㄋ械腉UI控件，如按鈕、組合框等，如QPushButton。擴(kuò)展的控件包括樹狀視圖、進(jìn)度條等, 如QListView。GUI組織類負(fù)責(zé)對(duì)各種控件進(jìn)行組織以構(gòu)成復(fù)雜的對(duì)話框, 如QGroupBox。幫助系統(tǒng)控件是為應(yīng)用程序提供在線幫助的類,QStatusBar,QToolTip?？蚣芸蚣懿糠职ǖ氖且恍┏橄蟮念?，通常不可見，如對(duì)象模型、抽象控件、繪圖、拖放、控件外觀。對(duì)象模型是框架的基礎(chǔ)，如QObject?？梢姷目丶话銖某橄罂丶缮?，如QButton。繪圖類控制繪圖, 如QBrush。拖放類控制拖放操作，如QDragObject。控件外觀類控制控件的外觀如顏色、字體等。例如QColor。工具工具部分包括時(shí)間日期和鏈表樹等數(shù)據(jù)結(jié)構(gòu),它們和GUI無關(guān)。普通工具包括鏈表、堆棧、隊(duì)列、樹等常見數(shù)據(jù)結(jié)構(gòu)，如QArray。圖形處理工具控制圖像的編碼/解碼算法。如QImageIO。I/O控制工具處理I/O的一些類，如QFile。時(shí)間和日期工具類處理時(shí)間和日期,如Qdate, QTime。另外還有其他雜類如Qsignal, QIconSet等。對(duì)象間通訊是面向?qū)ο蟪绦蛟O(shè)計(jì)的一個(gè)極其重要的內(nèi)容，類似于Microsoft MFC的消息映射和事件循環(huán)，Qt的對(duì)象間通訊采用的是信號(hào)—槽(signal—slot)機(jī)制，信號(hào)就好像是事件，而槽則是響應(yīng)事件的方法。如果需要實(shí)現(xiàn)對(duì)象間的通訊，只需要把一個(gè)對(duì)象的信號(hào)和另外一個(gè)對(duì)象的槽使用連接(connect)起來。信號(hào)—槽機(jī)制說明：Qt下對(duì)象間的通訊用信號(hào)—槽機(jī)制來實(shí)現(xiàn)。信號(hào)—槽機(jī)制是Qt的一個(gè)中心特征并且也是它與其它圖形工具包的最不相同的部分。下圖直觀地表示了這種機(jī)制是如何工作的。如圖216圖213在圖形用戶界面編程中，經(jīng)常希望一個(gè)窗口部件的一個(gè)變化被通知給另一個(gè)窗口部件。更一般地，希望任何一類對(duì)象可以和其它對(duì)象進(jìn)行通訊。例如，如果正在解析一個(gè)XML文件，當(dāng)遇到一個(gè)新的標(biāo)簽時(shí)，也許要通知列表視圖正在用來表達(dá)XML文件的結(jié)構(gòu)。較老的工具包是使用一種被稱作回調(diào)的通訊方式來實(shí)現(xiàn)同一目的。回調(diào)是指一個(gè)函數(shù)的指針，所以如果希望一個(gè)處理函數(shù)通知一些事件，可以把另一個(gè)函數(shù)(回調(diào))的指針傳遞給處理函數(shù)，處理函數(shù)在適當(dāng)?shù)臅r(shí)候調(diào)用回調(diào)函數(shù)?；卣{(diào)有兩個(gè)主要缺點(diǎn)：首先他們不是類型安全的，從來都不能確定處理函數(shù)使用了正確的參數(shù)來調(diào)用回調(diào)；其次回調(diào)和處理函數(shù)是非常強(qiáng)有力地聯(lián)系在一起的，因?yàn)樘幚砗瘮?shù)必須知道要調(diào)用哪個(gè)回調(diào)。在Qt中有一種可以替代回調(diào)的技術(shù)：使用信號(hào)和槽。當(dāng)一個(gè)特定事件發(fā)生的時(shí)候，一個(gè)信號(hào)被發(fā)射。Qt的窗口部件有很多預(yù)定義的信號(hào)，但是總是可以通過繼承來加入自己定義的信號(hào)。槽就是一個(gè)可以被調(diào)用處理特定信號(hào)的函數(shù)。Qt的窗口部件有很多預(yù)定義的槽，通常也可以加入自己的槽，這樣就可以處理感興趣的信號(hào)了。信號(hào)—槽機(jī)制是類型安全的