簡介《武漢理工大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法實驗——歡樂連連看非線性結(jié)構(gòu)》是一份面向高校數(shù)據(jù)結(jié)構(gòu)課程設(shè)計或算法綜合實踐的完整項目資源重點展示了二叉樹、圖、哈希表等非線性結(jié)構(gòu)在連連看游戲中的落地應(yīng)用適合計算機專業(yè)學(xué)生、課程實驗參考者及算法入門開發(fā)者參考學(xué)習(xí)。壓縮包為 7z 格式共 281 個文件整體約 226.97MB包含 Visual Studio 解決方案(.sln)、C 源文件(.cpp/.h)、編譯生成的可執(zhí)行文件(.exe)、位圖素材(.bmp)以及 Git 版本控制記錄等工程配置既有源碼也有可直接運行的程序。項目實現(xiàn)涉及 DFS/BFS 路徑搜索、最短路徑計算、哈希表狀態(tài)記錄等典型算法有助于理解非線性結(jié)構(gòu)如何解決實際匹配與消除問題。目前已有 2570 人學(xué)習(xí)/下載對于想通過趣味游戲項目鞏固數(shù)據(jù)結(jié)構(gòu)知識、查看完整工程結(jié)構(gòu)的讀者來說是一份具有參考價值的實踐樣本。1. 歡樂連連看從游戲規(guī)則看非線性數(shù)據(jù)結(jié)構(gòu)的實際意義很多同學(xué)拿到“數(shù)據(jù)結(jié)構(gòu)與算法實驗——歡樂連連看”這個題目時第一反應(yīng)是“這不就是個二維數(shù)組消消樂嗎哪里用到非線性結(jié)構(gòu)了”。如果你也這么想那這門實驗課大概率要翻車。連連看的棋盤確實長著一張“線性表”的臉——一個board[row][col]二維數(shù)組就能存下所有方塊但這只是表象。真正決定游戲體驗的是方塊與方塊之間那條蜿蜒的“連接路徑”這條路徑的搜索與合法性判斷依賴的是圖論中的廣度優(yōu)先遍歷思想而棋盤上有限連通區(qū)域的形成與坍塌又涉及連通分量與樹的層級關(guān)系。換句話說你用數(shù)組存棋盤用圖來思考連通用線性表做界面渲染三者缺一不可。該實驗被冠以“非線性結(jié)構(gòu)”之名核心考察點在于你能不能跳出for循環(huán)里一個個挨著比對的老套路把二維棋盤抽象成一個具有節(jié)點和邊的邏輯圖再在這個圖上設(shè)計路徑搜索策略。這也是本篇筆記存在的意義。我們把“歡樂連連看”拆成四層棋盤的數(shù)據(jù)映射、方塊的匹配規(guī)則、兩點之間拐點最少的路徑搜索、以及路徑搜索背后的 BFS/DFS 算法選型。四層全部打通你的實驗報告才真正有“非線性結(jié)構(gòu)”的內(nèi)味否則評委老師一眼就能看出你在拿線性表的遍歷硬湊圖論的結(jié)論。適合讀這篇筆記的讀者有三類第一類是正在為實驗報告發(fā)愁的在校生你需要一套能自圓其說的算法設(shè)計思路第二類是想要把課程設(shè)計做成“有點東西”的項目而不是交差就完事的同學(xué)這里附帶性能優(yōu)化與交互細節(jié)第三類是單純對“連連看算法”感興趣的編程愛好者這篇筆記能讓你少走大半年的彎路。下面的內(nèi)容我不會給你貼一大段所謂的“完整源碼”而是把構(gòu)成這個實驗的每一個決策點、每一段關(guān)鍵代碼、每一個讓你撓頭的邊界條件拆開揉碎。2. 棋盤的數(shù)據(jù)映射用圖而非數(shù)組來理解非線性關(guān)系2.1 二維數(shù)組的謊言為什么線性存儲掩蓋了節(jié)點間的真實聯(lián)系初次接觸連連看你會覺得這題簡單到離譜。定義一個int board[ROW][COL]0 表示空格非 0 表示方塊類型編號然后用兩層for循環(huán)遍歷整個棋盤判斷兩個方塊類型是否相同。聽起來完全符合線性表的操作范式但一旦你開始寫“判斷兩個方塊能否消除”的函數(shù)線性表思維就會立刻失效。因為連連看的消除條件不依賴于方塊本身的屬性而依賴于兩個方塊之間是否存在一條合法的路徑且這條路徑的拐點不得超過兩個。什么是拐點從方塊 A 到方塊 B如果能夠沿著同行或同列的水平/垂直線段移動路徑中的方向發(fā)生改變的位置就是一個拐點。直連是 0 拐點經(jīng)過一個中間轉(zhuǎn)換點橫線和豎線的交點是 1 拐點經(jīng)過兩個轉(zhuǎn)換點是 2 拐點。這個判斷邏輯跟數(shù)組索引的加減完全不在一個層面——它要求你把整個棋盤看作一個網(wǎng)絡(luò)每個空格都是一個通路節(jié)點每個方塊都是一個障礙節(jié)點兩個節(jié)點之間能否通信取決于節(jié)點之間的連通性。而“連通性”這三個字恰恰是圖論中最核心的概念也是線性表結(jié)構(gòu)無法直接表達的東西。我的做法是在動手寫任何算法之前先畫一張棋盤抽象圖。把二維坐標(biāo)(row, col)映射為圖中的節(jié)點 ID把相鄰的空白格子視為一條無向邊把有方塊的格子從圖中剔除。這樣一來“A 到 B 能否連通”就變成了“圖 G 中節(jié)點 A 到節(jié)點 B 是否存在一條路徑”。為了讓路徑搜索具備可行性通常我們還會在棋盤外圍補一層“虛擬空行”讓原本貼著棋盤邊界的方塊也能通過外部通道相連。這個“外圍擴展”的操作非常關(guān)鍵很多新手第一次寫連連看發(fā)現(xiàn)最左上角和最右下角的方塊明明能通過邊緣路徑相連程序卻認為它們不通原因就是忘記給棋盤加一圈外框。下面這段代碼展示了棋盤初始化與外圍擴展的標(biāo)準(zhǔn)姿勢。#define ROW 10 #define COL 10 #define EXTEND_ROW ROW 2 #define EXTEND_COL COL 2 int board[EXTEND_ROW][EXTEND_COL]; void init_board() { // 外圈全部置 0代表空白可通行區(qū)域 for (int i 0; i EXTEND_ROW; i) { board[i][0] 0; board[i][EXTEND_COL - 1] 0; } for (int j 0; j EXTEND_COL; j) { board[0][j] 0; board[EXTEND_ROW - 1][j] 0; } // 內(nèi)部填充方塊為 0 的位置表示已被消除 for (int i 1; i ROW; i) { for (int j 1; j COL; j) { // 模擬隨機生成不同類型方塊 board[i][j] rand() % 5 1; } } }這段代碼的邏輯很容易理解我們用一個比實際棋盤大一圈的二維數(shù)組來存儲游戲狀態(tài)所有邊界外的坐標(biāo)統(tǒng)一置為 0當(dāng)作可連通的空白區(qū)域。rand() % 5 1是臨時方案實際項目中會確保每種類型的方塊個數(shù)為偶數(shù)否則游戲后期必然出現(xiàn)無法消除的死局。參數(shù)層面EXTEND_ROW和EXTEND_COL的引入讓所有路徑搜索算法都不需要再做復(fù)雜的邊界判斷因為我們把“邊界外”這個特殊狀態(tài)變成了“空白格子”這個普通狀態(tài)極大簡化了后續(xù)代碼編寫。有人說這不還是在用二維數(shù)組嗎哪來的非線性結(jié)構(gòu)你需要換一個視角二維數(shù)組只是圖的一種存儲載體真正決定數(shù)據(jù)關(guān)系的是你如何在邏輯上解釋這個數(shù)組。在線性表語義下board[i][j]只跟它的索引相關(guān)在圖語義下board[i][j]跟它上下左右的鄰居節(jié)點相關(guān)這些鄰居關(guān)系構(gòu)成了邏輯上的鄰接鏈表。實驗要求里寫得清清楚楚你必須使用“非線性結(jié)構(gòu)”這里的非線性結(jié)構(gòu)指的不是你的存儲介質(zhì)而是你算法設(shè)計中對數(shù)據(jù)關(guān)系的組織方式——用圖的思維去指揮數(shù)組的操作。2.2 連通分量的應(yīng)用消除后棋盤會自動更新嗎棋盤上的方塊被消除后會留下一個空位。這個空位在邏輯上意味著一個障礙節(jié)點變成了通路節(jié)點。如果你在運行算法時重新遍歷整張圖來更新連通分量效率會非常低。實際操作中我們并不需要顯式維護一個完整的連通分量表因為每次判斷兩塊方塊是否連通時我們只關(guān)心局部路徑情況而不是全局連通性。但你是否想過當(dāng)一大批方塊被消除后圖中某些原本被阻斷的區(qū)域會突然連通這會不會影響后續(xù)的路徑判斷答案是不會影響正確性因為路徑搜索是實時進行的。每次判斷“A 與 B 是否可消”我們都會基于當(dāng)前棋盤狀態(tài)重新搜索路徑。操作順序上應(yīng)該是“先判斷路徑再執(zhí)行消除然后修改數(shù)組中對應(yīng)位置的值”。修改數(shù)組的動作永遠不會回溯到之前的搜索結(jié)果。這里有一個嚴重的認知誤區(qū)有些同學(xué)試圖維護一個“動態(tài)連通性數(shù)據(jù)結(jié)構(gòu)”每次消除后都重新計算全盤連通分量這完全背離了連連看的規(guī)則。連連看的核心約束是“兩點之間是否存在一條合法路徑”不是“兩個點是否屬于同一個連通區(qū)域”。屬于同一連通區(qū)域的兩點之間必然存在路徑但這條路徑的拐點數(shù)量可能大于 2而連連看要求不能超過 2 個拐點所以全局連通分量信息對你的搜索條件沒有任何幫助。這就是為什么我們不用并查集這類高級連通性結(jié)構(gòu)而是老老實實做局部搜索。圖示關(guān)系上請記住三條規(guī)則只有值為 0 的格子可以走路徑最多只能拐兩次路徑不能穿過任何有方塊或未消除的格子。這個映射關(guān)系一旦建立后面所有的代碼都會朝著“簡化路徑搜索”的方向演進而不是朝著“優(yōu)化連通性更新”的方向。這個決策決定了你的代碼結(jié)構(gòu)一個主控函數(shù)接收兩個坐標(biāo)調(diào)用內(nèi)部三個不同層級的判斷函數(shù)從易到難依次判定直連、一拐、兩拐。下一個章節(jié)我們詳細展開這三層判定函數(shù)的圖論本質(zhì)和代碼實現(xiàn)。3. 路徑搜索的層次遞進零拐點、單拐點與雙拐點的圖論推演3.1 直線可達與單拐點路徑從鄰接節(jié)點到中間節(jié)點的枚舉連連看的路徑搜索可以拆成三個遞進的層級每一層級都建立在前一層級的基礎(chǔ)上。最基礎(chǔ)的層級是直線可達。直線可達的判斷邏輯最簡單兩個方塊位于同一行或同一列且二者之間所有格子均為 0空白。寫成代碼就是遍歷兩者之間的所有坐標(biāo)逐一檢查board[i][j] 0。這段代碼沒有技術(shù)含量但它卻是整個連連看算法正確性的基石——因為后續(xù)所有復(fù)雜的拐彎路徑本質(zhì)上都是由一段段的直線段拼接而成的。單拐點路徑的判斷開始變得有趣。所謂單拐點是指從 A 出發(fā)先沿水平或垂直方向走到達某個中間點后轉(zhuǎn)向再沿垂直或水平方向到達 B。這個中間點有一個幾何特征它的橫坐標(biāo)與 A 相同或縱坐標(biāo)與 A 相同而縱坐標(biāo)與 B 相同或橫坐標(biāo)與 B 相同。換言之如果 A 的坐標(biāo)是(r1, c1)B 的坐標(biāo)是(r2, c2)那么候選的中間點就兩個(r1, c2)和(r2, c1)。你需要檢查這兩個中間點是否為空白以及 A 到中間點、中間點到 B 之間的兩條線段是否都是直線可達。算法的圖論本質(zhì)是在圖中枚舉 A 的所有“同行鄰居”和“同列鄰居”看能否通過這些鄰居中轉(zhuǎn)連接到 B。這里的關(guān)鍵優(yōu)化點在于你不用枚舉 A 所有的鄰居只需要枚舉兩個交點即可。但這兩個交點必須滿足“該交點本身是空白格子”。有些同學(xué)的代碼里漏掉了對中間點是否空白進行檢查結(jié)果出現(xiàn)方塊穿過方塊的神奇現(xiàn)象——兩條路徑明明被障礙物截斷程序卻判定連通。寫代碼時一定要把“線段上所有格子為 0 且中間點本身為 0”這一條件整合到同一個循環(huán)中避免分層判斷帶來的邏輯漏洞。看下面的實現(xiàn)。// 判斷兩個點之間的直線是否完全空 int is_line_empty(int r1, int c1, int r2, int c2) { // 同行 if (r1 r2) { int min_c c1 c2 ? c1 : c2; int max_c c1 c2 ? c1 : c2; for (int c min_c 1; c max_c; c) { if (board[r1][c] ! 0) return 0; // 有方塊阻擋 } return 1; } // 同列 else if (c1 c2) { int min_r r1 r2 ? r1 : r2; int max_r r1 r2 ? r1 : r2; for (int r min_r 1; r max_r; r) { if (board[r][c1] ! 0) return 0; } return 1; } return 0; // 既不同行也不同列直接返回 false } // 判斷單拐點路徑 int is_one_turn(int r1, int c1, int r2, int c2) { int mid_r r1, mid_c c2; // 中間點必須為空白 if (board[mid_r][mid_c] 0) { if (is_line_empty(r1, c1, mid_r, mid_c) is_line_empty(mid_r, mid_c, r2, c2)) { return 1; } } mid_r r2; mid_c c1; if (board[mid_r][mid_c] 0) { if (is_line_empty(r1, c1, mid_r, mid_c) is_line_empty(mid_r, mid_c, r2, c2)) { return 1; } } return 0; }這段代碼的參數(shù)定義非常樸素四個整型坐標(biāo)值分別代表兩個點的行和列。is_line_empty函數(shù)負責(zé)判斷兩個坐標(biāo)是否在同一行或同一列且路徑暢通它排除了首尾兩個點本身只檢查中間的格子。而is_one_turn函數(shù)則通過兩個候選中間點去測試能否通過一次轉(zhuǎn)彎連通。這里有一個我踩過的坑當(dāng)你把 A 的坐標(biāo)設(shè)為(r1, c1)、B 坐標(biāo)設(shè)為(r2, c2)時候選點(r1, c2)和(r2, c1)如果和 A 或 B 重合怎么辦比如 A 和 B 本就在同一行那(r1, c2)就是 B 自己(r2, c1)就是 A 自己。在這種邊界下is_one_turn會錯誤地返回 1因為它沿著“零長度路徑”連接。所以在調(diào)用is_one_turn之前你應(yīng)該在主函數(shù)中先判斷 A 和 B 是否同行或同列如果是直接走直線邏輯否則再進入拐點邏輯。這種分層管理的思路可以避免很多邊界條件互相干擾。3.2 雙拐點路徑的 BFS 搜索把枚舉問題轉(zhuǎn)化為層次遍歷問題雙拐點路徑的搜索是連連看的核心難點也是“非線性結(jié)構(gòu)”實驗報告的滿分關(guān)鍵。雙拐點的定義是路徑中恰好存在兩個轉(zhuǎn)向點。從圖論視角來看搜索雙拐點路徑等價于以下過程先讓 A 沿著所有可能的方向走一條直線水平或垂直走到某個中間點 M1再從 M1 沿著與其垂直的方向走一條直線走到另一個中間點 M2最后從 M2 沿著與 M1 方向垂直的方向走一條直線到 B。這個過程可以看作是一個受限的廣度優(yōu)先搜索從 A 出發(fā)先探索所有直線可達的節(jié)點再從這些節(jié)點出發(fā)探索與之垂直方向上的直線可達節(jié)點看最終能否覆蓋到 B。用枚舉法實現(xiàn)雙拐點搜索最樸素的方式是遍歷所有空白格子作為潛在拐點判斷 A 到中間點、中間點到 B 是否分別單拐可達。這種做法的復(fù)雜度為 O(N^2)對于 10x10 的棋盤尚可接受但如果你把棋盤擴展到 20x20 或帶有更多空白區(qū)域性能會急劇下降。而 BFS 的方法則聰明得多第一輪 BFS 從 A 出發(fā)向四個方向延伸把從 A 出發(fā)直線可達的連續(xù)空白格子全部標(biāo)記為“距離 1”第二輪 BFS 從這些已被標(biāo)記為“距離 1”的格子出發(fā)但方向和第一輪的方向垂直因為你要制造拐點繼續(xù)延伸并標(biāo)記為“距離 2”如果在第二輪延伸過程中覆蓋到了 B則說明雙拐點路徑存在。需要特別說明的是如果你用 DFS深度優(yōu)先搜索來做路徑搜索會存在路徑搜索過深導(dǎo)致時間開銷過大、甚至陷入死胡同的問題。連連看的路徑搜索必須是“層次感”明確的搜索BFS 天然契合這個需求。很多同學(xué)在這個地方走了彎路想著用 DFS 遞歸地朝四個方向試探結(jié)果要么棧溢出要么搜索路徑繞了很遠才發(fā)現(xiàn)死路。這是因為 DFS 無法保證搜索路徑的拐點數(shù)量最小化它可能找到一條拐了 10 次彎的路徑而你根本無法判斷它是否滿足“不超過兩個拐點”的約束。BFS 則不同BFS 天然具備“由近及遠”的搜索特征第一輪搜索保證找到距離為 1 的可達節(jié)點第二輪搜索保證找到距離為 2 的可達節(jié)點天然匹配連連看的拐點約束。typedef struct { int row; int col; } Point; // BFS 層次遍歷尋找兩拐連接 int is_two_turn_bfs(int r1, int c1, int r2, int c2) { int dir[4][2] {{1,0}, {-1,0}, {0,1}, {0,-1}}; int visited[EXTEND_ROW][EXTEND_COL] {0}; Point queue[EXTEND_ROW * EXTEND_COL]; int head 0, tail 0; // 第一輪從 A 出發(fā)向四個方向直線延伸 for (int i 0; i 4; i) { int nr r1 dir[i][0]; int nc c1 dir[i][1]; while (board[nr][nc] 0 nr 0 nr EXTEND_ROW nc 0 nc EXTEND_COL) { if (!visited[nr][nc]) { visited[nr][nc] 1; queue[tail].row nr; queue[tail].col nc; tail; } nr dir[i][0]; nc dir[i][1]; } } // 第二輪從第一輪找到的所有點出發(fā)沿垂直方向延伸 while (head tail) { Point cur queue[head]; head; for (int i 0; i 4; i) { int nr cur.row dir[i][0]; int nc cur.col dir[i][1]; if (nr r2 nc c2) return 1; // 直接到達 B while (nr 0 nr EXTEND_ROW nc 0 nc EXTEND_COL board[nr][nc] 0) { if (nr r2 nc c2) return 1; if (!visited[nr][nc]) { visited[nr][nc] 1; queue[tail].row nr; queue[tail].col nc; tail; } nr dir[i][0]; nc dir[i][1]; } } } return 0; }這段代碼有兩個極其容易翻車的細節(jié)。細節(jié)一while (board[nr][nc] 0 ...)循環(huán)的邊界條件必須先檢查數(shù)組下標(biāo)是否越界再檢查board值。C 語言中如果數(shù)組下標(biāo)越界你讀到的可能恰好是 0這會導(dǎo)致程序錯誤地繼續(xù)循環(huán)甚至訪問到完全不相關(guān)的內(nèi)存區(qū)域。細節(jié)二第二輪的“垂直方向”約束代碼里我依舊遍歷了全部 4 個方向這樣搜索范圍會擴大導(dǎo)致某些路徑實際上拐了 4 個彎也能被誤判為兩拐。所以你必須給第二輪加上一個判斷只能順著與第一輪不同的方向走。正確的做法是在dir數(shù)組中加入一個“方向來源”標(biāo)記更簡單的方式是第二輪時對cur點從它的“父方向”進行傳遞只沿垂直方向直線延伸。在我的實際項目中我會在入隊時順便記錄每個點第一次訪問到它時所用的方向然后第二輪搜索時限制方向為垂直于此方向的兩個方向只有這樣才能確保路徑拐點不超過 2。否則你得到的 BFS 結(jié)果會錯誤地放過一些不符合規(guī)則的路徑最終在老師人工驗盤時當(dāng)場翻車。3.3 直達、一拐、二拐的組合判定主控制函數(shù)的調(diào)度邏輯分層的搜索函數(shù)寫好后你需要一個主控制函數(shù)來綜合調(diào)度它們。這個主控函數(shù)是所有入口的統(tǒng)一收口無論是用戶點擊還是 AI 自動尋找最終都會調(diào)用它來判斷“可不可消”。調(diào)度順序上先調(diào)用is_line_empty判斷直線連接失敗后調(diào)用is_one_turn判斷單拐再次失敗后調(diào)用is_two_turn_bfs判斷雙拐。三層函數(shù)之間是短路求值的邏輯哪一層返回 1立即結(jié)束整個判斷流程不再繼續(xù)向下執(zhí)行。組合判定代碼的結(jié)構(gòu)如下。int can_connect(int r1, int c1, int r2, int c2) { if (board[r1][c1] ! board[r2][c2]) return 0; // 類型不同直接 false if (r1 r2 c1 c2) return 0; // 同一個方塊不能自消 // 層級 1直線 if (is_line_empty(r1, c1, r2, c2)) return 1; // 層級 2單拐 if (is_one_turn(r1, c1, r2, c2)) return 1; // 層級 3雙拐BFS if (is_two_turn_bfs(r1, c1, r2, c2)) return 1; return 0; }主控函數(shù)的邏輯不算復(fù)雜但有三個至關(guān)重要的前置條件很容易被忽略。第一任意兩個坐標(biāo)方塊的類型必須相同這個判斷必須在路徑搜索之前完成否則你很可能搜索出一條路徑結(jié)果兩端方塊花色不一樣白白浪費計算資源。第二兩個坐標(biāo)不能是同一個點這個判斷看似多余但在 UI 交互中用戶可能誤點同一個方塊兩次如果不攔截is_line_empty會返回 1造成誤消除。第三也是最隱蔽的board[r1][c1]本身不能為 0也就是說已經(jīng)消除的位置不能再次被當(dāng)作起點或終點參與匹配——一個空格子是不可能被消除的。有些同學(xué)在代碼中只判斷了類型相同忘了檢查起點和終點本身是否為空格結(jié)果出現(xiàn)了“消除空氣”的詭異 bug。4. 代碼實現(xiàn)的骨架搭建從控制臺到交互界面4.1 數(shù)據(jù)結(jié)構(gòu)的統(tǒng)一定義與全局狀態(tài)管理在一個完整的實驗項目中代碼的組織往往比算法本身更決定成敗。很多同學(xué)的實驗代碼只有可憐的main函數(shù)加三個子函數(shù)看的人一頭霧水寫的人自己過兩天也看不懂。為了給實驗報告和答辯做準(zhǔn)備最好把代碼按職責(zé)分層數(shù)據(jù)層、算法層、交互層。數(shù)據(jù)層負責(zé)維護全局的棋盤狀態(tài)數(shù)組和方塊類型映射表算法層集中實現(xiàn)路徑搜索的多個函數(shù)交互層負責(zé)接收用戶輸入、刷新界面、執(zhí)行消除動作并觸發(fā)勝利判定。typedef struct { int type; // 方塊類型 1-5 int eliminated; // 0 表示存在1 表示已消除 } Block; typedef struct { Block cells[EXTEND_ROW][EXTEND_COL]; int remain_count; // 剩余未消除方塊數(shù)量 int score; // 計分 } GameState; GameState game; void reset_game() { memset(game, 0, sizeof(game)); // 內(nèi)部區(qū)域填充方塊 for (int i 1; i ROW; i) { for (int j 1; j COL; j) { game.cells[i][j].type rand() % 5 1; game.cells[i][j].eliminated 0; game.remain_count; } } }Block結(jié)構(gòu)體的設(shè)計體現(xiàn)了一個很好的抽象思維每個格子除了存類型還存一個“是否已被消除”的狀態(tài)。為什么不用數(shù)組的值 0 來表示消除因為類型可能也用 0 表示空容易混。一旦類型和狀態(tài)分離你就不需要擔(dān)心語義重疊的問題。在算法層讀取格子時統(tǒng)一檢查eliminated字段在渲染層打印時根據(jù)eliminated決定打印方塊圖案還是空白區(qū)域。這種基于結(jié)構(gòu)體的封裝讓代碼的可讀性提高了好幾個檔次。而全局狀態(tài)管理上GameState結(jié)構(gòu)體承擔(dān)了所有全局狀態(tài)的聚合。只要改變這個結(jié)構(gòu)體整個游戲的狀態(tài)就會同步更新不需要在各種函數(shù)之間傳遞大量的參數(shù)。這在程序規(guī)模變大時尤為有效。很多同學(xué)喜歡把棋盤數(shù)組、剩余個數(shù)、分數(shù)全部定義成獨立的全局變量這在小型 Demo 中尚可但一旦要加入計時器、道具、悔棋等高級功能全局變量就會變成一團亂麻。把所有狀態(tài)收攏到一個結(jié)構(gòu)體里是新手向熟手過渡的關(guān)鍵一步。4.2 渲染與交互把控制臺輸出變成可玩的游戲循環(huán)如果實驗允許使用圖形界面建議優(yōu)先選擇簡單的控制臺 ANSI 圖形或輕量級的圖形庫?？刂婆_輸出的方式是很多同學(xué)的首選因為它不需要搭建復(fù)雜的環(huán)境只需要在循環(huán)中不斷清屏、打印當(dāng)前棋盤狀態(tài)就可以了。交互邏輯上等待用戶輸入兩個方塊的坐標(biāo)調(diào)用can_connect判斷如果返回 1 則執(zhí)行消除動作并更新界面否則提示“無法連接”。void render_board() { system(cls); // Windows 環(huán)境清屏函數(shù) printf( ); for (int c 1; c COL; c) printf(%4d , c); printf(\n); for (int i 1; i ROW; i) { printf(%3d , i); for (int j 1; j COL; j) { if (game.cells[i][j].eliminated) { printf( ·); // 空白占位符 } else { printf(%4d , game.cells[i][j].type); } } printf(\n); } printf(剩余方塊數(shù): %d\n, game.remain_count); } void game_loop() { int x1, y1, x2, y2; while (game.remain_count 0) { render_board(); printf(請輸入第一個方塊坐標(biāo) (row col): ); scanf(%d %d, x1, y1); printf(請輸入第二個方塊坐標(biāo) (row col): ); scanf(%d %d, x2, y2); if (can_connect(x1, y1, x2, y2)) { game.cells[x1][y1].eliminated 1; game.cells[x1][y1].type 0; game.cells[x2][y2].eliminated 1; game.cells[x2][y2].type 0; game.remain_count - 2; game.score 10; printf(消除成功當(dāng)前得分%d\n, game.score); } else { printf(無法消除請重新選擇。\n); } system(pause); // 防止界面閃退 } printf(恭喜通關(guān)最終得分%d\n, game.score); }這段代碼的交互邏輯非常直觀。scanf獲取坐標(biāo)后由can_connect統(tǒng)一判斷成功后執(zhí)行兩個eliminated標(biāo)記并更新剩余方塊數(shù)。這里有一個通用做法需要提醒坐標(biāo)輸入的合法性檢查不能省略。用戶可能輸入負數(shù)、超過棋盤范圍的數(shù)甚至輸入 0這些都會導(dǎo)致數(shù)組越界訪問程序直接崩潰。代碼中應(yīng)該在can_connect判斷之前增加一個if (x1 1 || x1 ROW || y1 1 || y1 COL || ...)的白名單校驗。此外system(cls)在 Windows 下有效但在 Linux 下需要換成system(clear)如果你跨平臺編譯建議用宏定義預(yù)處理指令來區(qū)分平臺。這不屬于算法核心但絕對影響實驗演示效果——如果你在答辯時用的是 Mac 電腦而代碼里寫著cls畫面就會花成一片老師的第一印象會打折扣。4.3 消除后的連鎖響應(yīng)與死局檢測機制連連看還有一個容易忽略的點死局檢測。當(dāng)棋盤上仍有方塊但任意兩個相同類型的方塊都無法通過合法路徑相連時游戲就進入了死局。大多數(shù)課程設(shè)計只要求做到判斷兩個方塊不要求處理死局但如果你想讓項目在答辯時脫穎而出把死局檢測加上絕對是加分項。死局檢測的樸素做法是遍歷所有剩余方塊對對每一對執(zhí)行can_connect只要有一對可以消除立即返回“未死局”。時間復(fù)雜度在最壞情況下是 O(N^4)對 10x10 棋盤來說完全可接受。優(yōu)化做法是用哈希表按方塊類型分組只對類型相同的方塊對進行判斷這樣檢測速度會快很多。死局出現(xiàn)后比較穩(wěn)妥的處理策略是給用戶兩個選項重新洗牌或者重新開局。洗牌操作指的是將棋盤上所有剩余的方塊打亂重排但要保證每個類型的數(shù)量不變且洗出來的局面不是死局。int is_deadlock() { int type_count[6] {0}; // 假設(shè)類型為 1-5 for (int i 1; i ROW; i) { for (int j 1; j COL; j) { if (!game.cells[i][j].eliminated) { type_count[game.cells[i][j].type]; } } } for (int t 1; t 5; t) { if (type_count[t] 0) continue; // 收集所有類型為 t 的未消除點 Point pts[100]; int pn 0; for (int i 1; i ROW; i) { for (int j 1; j COL; j) { if (!game.cells[i][j].eliminated game.cells[i][j].type t) { pts[pn].row i; pts[pn].col j; pn; } } } for (int i 0; i pn; i) { for (int j i 1; j pn; j) { if (can_connect(pts[i].row, pts[i].col, pts[j].row, pts[j].col)) { return 0; // 發(fā)現(xiàn)一對可以消未死局 } } } } return 1; // 所有同類型對都不可消死局 }死局檢測函數(shù)的存在讓游戲的主循環(huán)必須多一層判斷。每完成一次消除、刷新界面之前先調(diào)用is_deadlock檢測。如果返回 1提示用戶選擇重新洗牌還是結(jié)束游戲。這套機制確保了用戶不會面對一個“看起來還有方塊卻什么都點不動”的迷茫狀態(tài)。很多商業(yè)連連看產(chǎn)品中死局自動洗牌是標(biāo)配功能你的實驗項目中哪怕只做一個手動觸發(fā)按鈕也足以體現(xiàn)你對用戶體驗的思考深度。5. 避坑指南連連看實驗里 5 個讓人抓狂的隱蔽問題5.1 拐點計數(shù)偏移用 BFS 時不記錄方向?qū)е抡`判現(xiàn)象明明兩塊方塊之間需要拐三個彎程序卻返回可以消除反過來有些只需要拐兩個彎的路徑反而判不出來。原因很多同學(xué)寫著寫著就把雙拐 BFS 寫成了“無限拐彎 BFS”因為 BFS 擴展時向四個方向同時掃描不加方向約束。第一輪從 A 出發(fā)向四個方向延伸第二輪又從第一輪得到的點向四個方向延伸這樣搜索出來的路徑實際上是無限制拐彎的你根本沒有辦法保證路徑拐點數(shù)量不超過 2。解決給每個節(jié)點增加“來源方向”字段。初始化時A 點的來源方向為 -1第一輪擴展出的點記錄它們的前進方向第二輪擴展時只沿著與來源方向垂直的兩個方向繼續(xù)擴展。同時需要在每一輪的目標(biāo)檢查中確認是否到達 B到達 B 即返回成功。如果你使用上述is_two_turn_bfs的樸素版本請務(wù)必手動打補丁加上方向限制。這個 bug 極其隱蔽普通的測試用例測不出來但一旦遇到拐了三次彎才連通的棋盤布局你的算法就翻車了。5.2 數(shù)組越界訪問外圍擴展后忘記同步修改所有函數(shù)現(xiàn)象棋盤初始化時明明留了一圈擴展邊界但運行中偶爾出現(xiàn)莫名其妙的“額外方塊”或者方塊消失后無法再連接。原因你的外圍擴展只改了init_board函數(shù)但is_line_empty、is_one_turn、is_two_turn_bfs函數(shù)里依然使用ROW和COL作為邊界。循環(huán)變量從0到ROW會漏掉最邊緣的一行導(dǎo)致邊緣上的空白格子永遠不被檢測為可通行區(qū)域。解決檢查全工程中所有涉及棋盤遍歷的代碼統(tǒng)一使用EXTEND_ROW和EXTEND_COL作為邊界常量。同時保證所有循環(huán)的索引從0開始而不是從1開始因為擴展邊界在0和EXTEND_ROW - 1。統(tǒng)一邊界的使用對后續(xù)擴展功能有百利而無一害。這個“改一處忘一處”的錯誤在多人協(xié)作或復(fù)制粘貼代碼時發(fā)生了無數(shù)次每換一次函數(shù)就要多檢查一遍邊界。5.3 死局誤判與洗牌邏輯類型數(shù)量丟失導(dǎo)致無法通關(guān)現(xiàn)象游戲卡在死局狀態(tài)但玩家明明還有可以消除的對子或者點擊洗牌后棋盤上的方塊種類數(shù)量變得不均勻出現(xiàn)最后剩兩個相同方塊但連接不上的死局。原因is_deadlock函數(shù)在統(tǒng)計類型數(shù)量時把已消除方塊eliminated 1也算進去了導(dǎo)致誤判。而洗牌邏輯在重新分配方塊類型時沒有嚴格統(tǒng)計當(dāng)前剩余每種方塊的數(shù)量而是用rand() % 5 1重新生成導(dǎo)致某些類型變多、某些類型變少。解決修正type_count統(tǒng)計邏輯只累加!eliminated的格子洗牌時先收集所有未消除方塊的類型存入一個臨時數(shù)組再用隨機亂序算法如 Knuth 洗牌打亂這個數(shù)組最后按順序重新填充到棋盤上未消除的位置。這樣保證每種方塊數(shù)量不變具有成為可完成局面的基本條件。另外洗牌后的新棋盤還要再次執(zhí)行is_deadlock檢測如果仍是死局則再次洗牌直到找到一個非死局面為止。這個循環(huán)理論上存在死循環(huán)的微小概率極稀疏棋盤可加一個最大重試次數(shù)超時后直接判定游戲結(jié)束。5.4 重復(fù)點擊與快速消除交互層沒有鎖定狀態(tài)現(xiàn)象玩家快速雙擊第二個方塊時程序有時會連續(xù)消掉兩個不同的對子導(dǎo)致計分錯誤或者在消除路徑尚未繪制完成時棋盤狀態(tài)處于中間態(tài)玩家點擊到的坐標(biāo)已經(jīng)變化。原因在交互層沒有引入“處理中”或“鎖定”的概念。can_connect調(diào)用成功后需要立即標(biāo)記兩個方塊為eliminated這個動作應(yīng)該是原子的。如果你的代碼在輸出路徑動畫后才去修改eliminated那么在這段動畫期間棋盤上的數(shù)據(jù)是未同步的玩家就能趁機點擊到尚未消除的方塊邏輯混亂。解決最簡單的辦法是在消除成功后立即將eliminated置為 1不等待動畫完成。動畫只是視覺渲染層面的效果不應(yīng)該影響狀態(tài)變更。在代碼中設(shè)置一個全局標(biāo)志位is_processing點擊事件觸發(fā)時先檢查這個標(biāo)志位如果為真則忽略本次輸入。消除執(zhí)行結(jié)束后再將標(biāo)志位復(fù)位。這個小改動能讓你的程序在快速點擊下依然保持穩(wěn)定。5.5 隨機生成的方塊數(shù)量不成對最后一對永遠無法消除現(xiàn)象游戲運行到最后剩余方塊的數(shù)量是奇數(shù)或者每種方塊剩余數(shù)量是奇數(shù)導(dǎo)致無論如何都不可能全部消除。原因初始化棋盤時直接用了rand() % 5 1無腦填充沒有保證每個類型出現(xiàn)的次數(shù)是偶數(shù)。連連看的規(guī)則決定每消一次必須移除兩個相同類型的方塊所有類型的總數(shù)必須為偶數(shù)否則游戲必然結(jié)束在死局狀態(tài)。解決在初始化階段生成兩個相同類型的候選組交替放入棋盤。具體做法是計算總方塊數(shù)ROW * COL確保它是偶數(shù)創(chuàng)建一個類型數(shù)組按順序放入ROW * COL / 2對重復(fù)的類型值再用 Knuth 洗牌算法打亂最后填充到棋盤內(nèi)部區(qū)域。這個方法既保證了每種類型數(shù)量成對也保證了方塊分布的隨機性。這是整個實驗中最基礎(chǔ)也最容易被忽視的點一旦前期沒處理好后期無論算法多正確都無法通關(guān)。6. 把實驗做成作品路徑可視化、隨機提示與答辯話術(shù)最后一個章節(jié)聊點能讓你的實驗從“能跑”變成“好看”的技巧。課程設(shè)計的評分標(biāo)準(zhǔn)通常包含兩部分功能完整性和展示效果。功能完整性方面前五章已經(jīng)覆蓋展示效果方面你需要給評委看到你在細節(jié)上的投入。一個經(jīng)驗豐富的評委在五分鐘的答辯時間內(nèi)到底會關(guān)注什么他不會一行行讀你的源碼他只會做三件事運行程序看流暢度、隨機點幾下看是否有明顯 bug、問你幾個算法設(shè)計上的決策問題。路徑可視化是最容易出彩的優(yōu)化點。在控制臺版本中當(dāng)你判斷出兩個方塊可以消除后不要立刻消除而是先把這條路徑上的所有中間點用特殊符號比如*繪制出來停留幾百毫秒再消除。這個視覺效果能非常直觀地展示你的算法運行過程評委一看就知道你用的是“真算法”而不是“假遍歷”。在is_two_turn_bfs中每找到一個有效中間點就把它的坐標(biāo)存入一個臨時數(shù)組路徑確認后統(tǒng)一渲染。如果你使用圖形界面庫這就是在兩點之間畫一根折線的問題實現(xiàn)成本極低但視覺沖擊力極強。同時這也能幫助你在調(diào)試時一眼看出路徑搜索是否符合拐點約束。隨機提示功能可以說是用戶體驗的點睛之筆。當(dāng)玩家卡住的時候按 H 鍵隨機選擇一對可消除的方塊并高亮顯示這本質(zhì)上是一次“重復(fù)調(diào)用is_deadlock并返回第一個可連接對”的操作。你可以用一個額外函數(shù)find_hint()遍歷所有同類型的方塊對返回第一對能夠通過can_connect的坐標(biāo)。在實際項目中光有這個功能還不夠還需要把它和被卡住狀態(tài)做一個聯(lián)動如果is_deadlock()返回 1提示用戶選擇洗牌如果沒有死局但用戶連續(xù)多次無效點擊說明他可能暫時找不到此時“向用戶推薦一對”可以極大提升體驗。這個細節(jié)在功能性實驗中不加分但在工程化評估中絕對加分。至于答辯時的技術(shù)陳述核心有一條主線把二維數(shù)組當(dāng)作圖的存儲底層把路徑搜索當(dāng)作圖的遍歷。答辯老師問到“非線性結(jié)構(gòu)體現(xiàn)在哪”你可以說“棋盤中每個格子是圖的一個節(jié)點格子的相鄰關(guān)系是圖的邊路徑搜索就是廣度優(yōu)先遍歷的一種受限應(yīng)用”。問到“為什么用 BFS 而不是 DFS”你可以說“BFS 天生保證找到最短路徑滿足拐點次數(shù)限制DFS 則可能找到過回路徑導(dǎo)致誤判”。這段話術(shù)能夠把你的代碼從“二維數(shù)組的遍歷技巧”拔高到“非線性結(jié)構(gòu)的應(yīng)用”正好呼應(yīng)實驗標(biāo)題。最后分享一下我自己做這個實驗時的一個習(xí)慣永遠在提交前做一輪“極限布局測試”。手動創(chuàng)建一個只有兩個同類型方塊、其余全空的棋盤確認它們能連接創(chuàng)建一個兩個同類型方塊被其他方塊包圍成環(huán)的棋盤確認它們不能連接創(chuàng)建一個充滿隨機方塊但刻意讓最后兩個方塊同類型的棋盤跑完整局確認不會出現(xiàn)無解局面。這三個極端測試用例通過基本能覆蓋絕大多數(shù)隱藏問題。每次寫完一個模塊我都會先跑這三個用例再開始寫下一個模塊而不是全部寫完再一次調(diào)。這個習(xí)慣幫我避開了無數(shù)個把自己繞暈的 bug。希望這些經(jīng)驗?zāi)軒偷侥阕屇愕倪B連看實驗不再只是應(yīng)付差事而是成為一份真正拿得出手的作品。本文還有配套的精品資源點擊獲取