簡(jiǎn)介武漢理工大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)的歡樂連連看項(xiàng)目以游戲?yàn)檩d體系統(tǒng)訓(xùn)練非線性結(jié)構(gòu)的綜合運(yùn)用適合計(jì)算機(jī)專業(yè)學(xué)生、課程設(shè)計(jì)參考者及需要?jiǎng)邮掷斫鈽?、圖、哈希表的開發(fā)者。壓縮包共281個(gè)文件、約227MB核心由9個(gè)cpp源碼和13個(gè)h頭文件組成附帶Visual Studio解決方案配置、exe可執(zhí)行文件、編譯中間文件及bmp/ico圖像資源Git倉庫對(duì)象也完整保留可作為版本管理學(xué)習(xí)素材。目前已有2570人瀏覽學(xué)習(xí)。項(xiàng)目完整實(shí)現(xiàn)連連看核心玩法包括鄰接矩陣/鄰接表建模、圖案匹配與消除判定、DFS/BFS搜索路徑等模塊便于對(duì)照源碼觀察非線性結(jié)構(gòu)在真實(shí)游戲邏輯中的運(yùn)行流程?？芍苯舆\(yùn)行exe驗(yàn)證效果也能基于sln重新編譯調(diào)試對(duì)數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)和期末設(shè)計(jì)都有較高參考價(jià)值。1. 連連看實(shí)驗(yàn)到底在考什么非線性結(jié)構(gòu)不是難點(diǎn)建模才是某高校的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)里連連看通常是“非線性結(jié)構(gòu)”那一章的大作業(yè)標(biāo)題還帶著“歡樂”兩個(gè)字聽起來比寫紅黑樹輕松實(shí)際上翻車率并不低。很多人第一反應(yīng)是找一份現(xiàn)成的連連看源碼跑起來結(jié)果發(fā)現(xiàn)評(píng)分里一半分?jǐn)?shù)落在“結(jié)構(gòu)設(shè)計(jì)說明”上另一半在搜索算法的正確性。這個(gè)實(shí)驗(yàn)真正的考點(diǎn)不是做一個(gè)能玩的游戲而是把“兩個(gè)圖案能否消除”這件事抽象成一張圖再在圖模型上做路徑搜索。棋盤格子之間的連通關(guān)系屬于拓?fù)潢P(guān)系不是線性表能直接表達(dá)的這正是“非線性結(jié)構(gòu)”四個(gè)字想讓你動(dòng)用的東西。如果你是正在做這個(gè)實(shí)驗(yàn)、或者打算做但還沒想清楚數(shù)據(jù)結(jié)構(gòu)怎么選這篇能給你一條走得通的落地路徑。我自己的習(xí)慣是先寫判定函數(shù)再寫界面層順序反了會(huì)一直陷在顯示層的泥潭里。2. 給連連看建立圖模型二維數(shù)組存棋盤BFS 解決連通判定2.1 為什么棋盤要用二維數(shù)組而不是鏈表連連看的棋盤是固定行列的網(wǎng)格最常見的做法是直接用vectorvectorint或者二維數(shù)組來存。每個(gè)格子存一個(gè)整數(shù)值0 表示空格非 0 表示某種圖案的編號(hào)。這個(gè)選擇背后是有理由的連連看的搜索核心是“從一個(gè)格子出發(fā)判斷能否到達(dá)另一個(gè)格子”這要求對(duì)任意坐標(biāo)的讀取是 O(1)二維數(shù)組天然滿足。鏈表結(jié)構(gòu)在插入刪除上有優(yōu)勢(shì)但連連看棋盤在游戲過程中只有“某個(gè)格子從圖案變成空格”這一種修改數(shù)組同樣能 O(1) 完成鏈表反而會(huì)讓坐標(biāo)尋址變得別扭。圖模型在這里是隱式的把每個(gè)非空格子看成一個(gè)頂點(diǎn)把相鄰的空格子之間的通行關(guān)系看成邊棋盤就形成了一張網(wǎng)格圖。值得注意的是這張圖是動(dòng)態(tài)變化的——每消除一對(duì)圖案就有兩個(gè)頂點(diǎn)從“不可通行”變成“可通行”。所以在寫搜索算法時(shí)棋盤數(shù)據(jù)必須是搜索函數(shù)的輸入?yún)?shù)而不是全局變量里一份被界面反復(fù)改動(dòng)的副本。常見做法是維護(hù)一份board作為唯一數(shù)據(jù)源判定函數(shù)每次接收當(dāng)前局面的拷貝或引用。2.2 搜索算法選型為什么首選 BFS 而不是 DFS連連看的消除規(guī)則是兩個(gè)相同圖案之間能用不超過三段直線段連接也就是路徑最多拐兩次彎。這里有一個(gè)關(guān)鍵誤區(qū)——大部分人會(huì)下意識(shí)去找“最短路徑”以為路徑越短越能消除但規(guī)則根本不看路徑長(zhǎng)度只看拐彎次數(shù)。于是問題轉(zhuǎn)化成在網(wǎng)格圖上找一條從起點(diǎn)到終點(diǎn)的路徑使得方向變化的次數(shù)不超過 2。BFS 在這里是天然匹配的。把“拐彎次數(shù)”當(dāng)作路徑代價(jià)直行代價(jià)為 0拐彎代價(jià)為 1那么這就是一個(gè)邊權(quán)只有 0 和 1 的最短路問題。普通 BFS 隊(duì)列能處理邊權(quán)為 1 的圖但處理不了邊權(quán)為 0 的情況所以這里需要用一點(diǎn)小變體把狀態(tài)擴(kuò)展分為“先直行到底再拐彎”的層序處理或者直接用 0-1 BFS雙端隊(duì)列。在棋盤尺寸不大比如 10x10 到 16x14的前提下實(shí)現(xiàn)一個(gè)帶拐彎計(jì)數(shù)的普通 BFS 也完全可行只需要在狀態(tài)里多記錄當(dāng)前方向和已經(jīng)拐了幾次。DFS 為什么不推薦因?yàn)?DFS 會(huì)沿著一條路走到底很容易走進(jìn)死胡同而且為了找到“拐彎不超過 2”的路徑DFS 需要回溯大量分支狀態(tài)爆炸的概率遠(yuǎn)高于 BFS。在棋盤搜索這種場(chǎng)景下BFS 的層序擴(kuò)展能保證第一次遇到終點(diǎn)時(shí)的拐彎次數(shù)就是最小的DFS 沒法保證這一點(diǎn)。實(shí)際實(shí)驗(yàn)中用 DFS 寫的判定函數(shù)經(jīng)常出現(xiàn)“明明能消除卻判定不可達(dá)”的問題排查起來極其痛苦。2.3 狀態(tài)設(shè)計(jì)方向 拐彎次數(shù)才是完整的狀態(tài)初寫 BFS 的人最容易犯的錯(cuò)誤是只用一個(gè)二維visited數(shù)組記錄格子是否訪問過。這在普通最短路里沒問題但在拐彎約束下是不夠的。同一個(gè)格子從左邊進(jìn)入和從上方進(jìn)入后續(xù)可走的路徑集合完全不同就算到達(dá)同一個(gè)格子的拐彎次數(shù)相同只要進(jìn)入方向不同后續(xù)能擴(kuò)展的分支就不同。所以visited必須升級(jí)成三維標(biāo)記vis[x][y][dir]表示在坐標(biāo)(x,y)處、當(dāng)前朝向?yàn)閐ir時(shí)的最小拐彎次數(shù)。我用的是四方向編號(hào)0 上、1 下、2 左、3 右。狀態(tài)結(jié)構(gòu)體里存三個(gè)字段坐標(biāo)、當(dāng)前方向、已拐彎次數(shù)。從起點(diǎn)出發(fā)時(shí)沒有方向可以枚舉四個(gè)方向作為初始狀態(tài)每個(gè)方向的拐彎次數(shù)從 0 開始。轉(zhuǎn)移時(shí)如果下一步的方向和當(dāng)前方向一致拐彎次數(shù)不變?nèi)绻灰恢鹿諒澊螖?shù)加 1超過上限 2 就剪枝。這個(gè)“方向變化才計(jì)數(shù)”的模型是連連看判定算法的核心也是后面所有坑的源頭。3. 消除判定算法的完整實(shí)現(xiàn)狀態(tài)搜索與邊界處理3.1 核心 BFS 路徑搜索代碼先給出判定兩個(gè)格子能否消除的完整函數(shù)實(shí)現(xiàn)。這里用雙端隊(duì)列做 0-1 BFS直行優(yōu)先擴(kuò)展保證拐彎次數(shù)最小時(shí)盡早命中終點(diǎn)。#include deque #include vector using namespace std; struct State { int x, y; // 當(dāng)前格子坐標(biāo) int dir; // 當(dāng)前移動(dòng)方向0上 1下 2左 3右 int turns; // 已經(jīng)拐彎的次數(shù) }; // board: 棋盤數(shù)據(jù)board[x][y] 0 表示空格非0表示圖案編號(hào) // 判斷 (sx, sy) 與 (ex, ey) 兩個(gè)格子是否能在拐彎不超過2次內(nèi)連通 bool canConnect(const vectorvectorint board, int sx, int sy, int ex, int ey) { if (board[sx][sy] 0 || board[ex][ey] 0) return false; if (board[sx][sy] ! board[ex][ey]) return false; if (sx ex sy ey) return false; int rows board.size(); int cols board[0].size(); int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; // vis[x][y][dir] 記錄到達(dá) (x,y) 且朝向?yàn)?dir 時(shí)的最小拐彎次數(shù) // 初始化為 -1 表示未訪問 vectorvectorvectorint vis( rows, vectorvectorint(cols, vectorint(4, -1))); // 0-1 BFS拐彎少的狀態(tài)優(yōu)先從隊(duì)頭出隊(duì) dequeState dq; // 起點(diǎn)本身不可作為路徑經(jīng)過點(diǎn)從起點(diǎn)的四個(gè)相鄰格子開始擴(kuò)展 for (int d 0; d 4; d) { int nx sx dx[d], ny sy dy[d]; if (nx 0 || nx rows || ny 0 || ny cols) continue; // 相鄰格子是終點(diǎn)時(shí)方向一致且不需要經(jīng)過空格 if (nx ex ny ey) return true; // 只有空格可以經(jīng)過 if (board[nx][ny] ! 0) continue; vis[nx][ny][d] 0; dq.push_back({nx, ny, d, 0}); } while (!dq.empty()) { State cur dq.front(); dq.pop_front(); for (int nd 0; nd 4; nd) { int nx cur.x dx[nd], ny cur.y dy[nd]; if (nx 0 || nx rows || ny 0 || ny cols) continue; // 到達(dá)終點(diǎn)終點(diǎn)本身可以是圖案格不需要是空格 if (nx ex ny ey) { int nt cur.turns (nd ! cur.dir ? 1 : 0); if (nt 2) return true; continue; } // 路徑經(jīng)過的格子必須是空格 if (board[nx][ny] ! 0) continue; int nt cur.turns (nd ! cur.dir ? 1 : 0); if (nt 2) continue; // 只有更優(yōu)的拐彎次數(shù)才繼續(xù)擴(kuò)展 if (vis[nx][ny][nd] -1 || nt vis[nx][ny][nd]) { vis[nx][ny][nd] nt; if (nd ! cur.dir) { dq.push_back({nx, ny, nd, nt}); } else { dq.push_front({nx, ny, nd, nt}); } } } } return false; }這段代碼的三個(gè)關(guān)鍵設(shè)計(jì)要說明一下。第一起點(diǎn)的相鄰格子如果正好是終點(diǎn)直接返回 true這是“兩格緊挨著”的消除場(chǎng)景不需要經(jīng)過任何空格。第二終點(diǎn)判斷放在障礙判斷之前因?yàn)榻K點(diǎn)本身是有圖案的格子不能被當(dāng)成障礙攔掉這是很容易寫反的地方。第三用雙端隊(duì)列做 0-1 BFS方向不變的狀態(tài)放入隊(duì)頭優(yōu)先擴(kuò)展拐彎的狀態(tài)放入隊(duì)尾這樣能更快找到拐彎次數(shù)少的路徑同時(shí)也避免普通 BFS 里同層擴(kuò)展順序?qū)Y(jié)果的影響。3.2 邊界處理路徑能否走出棋盤一個(gè)容易被忽略的問題是路徑能不能經(jīng)過棋盤外部的區(qū)域多數(shù)網(wǎng)絡(luò)上的連連看實(shí)現(xiàn)不允許路徑走出棋盤但某些變體規(guī)則允許連線繞過棋盤邊緣。我的建議是實(shí)驗(yàn)里明確寫成“不允許出界”因?yàn)轭}目通常只要求在棋盤內(nèi)部尋找路徑而且允許出界的搜索需要額外處理虛擬外圈代碼復(fù)雜度會(huì)明顯上升。上面給出的版本是不允許出界的。如果你想讓路徑允許貼邊繞行有一個(gè)取巧的辦法在原棋盤四周加一圈全 0 的虛擬格子搜索時(shí)把邊界擴(kuò)大到rows2、cols2這樣路徑就能“走出棋盤”了。但要注意終點(diǎn)和起點(diǎn)的坐標(biāo)也要相應(yīng)偏移否則坐標(biāo)映射會(huì)亂。我見過有人在答辯時(shí)被老師問“邊界情況怎么處理”答不出“外圈虛擬空格”方案這就是平時(shí)沒想過的細(xì)節(jié)。3.3 參數(shù)設(shè)計(jì)一行代碼控制游戲難度搜索算法本身的參數(shù)不多真正影響難度的是棋盤尺寸和圖案種類數(shù)。棋盤越大、圖案種類越多可消除的對(duì)越少死局概率越高。一個(gè)比較穩(wěn)的參數(shù)組合是8 行 10 列配 5 種圖案或者 10 行 12 列配 6 種圖案。圖案種類數(shù)的上限要滿足rows * cols / 2能整除種類數(shù)否則圖案數(shù)量不平衡必然出現(xiàn)“某一個(gè)圖案多一個(gè)”的生成錯(cuò)誤。// 參數(shù)配置示例 int rows 10, cols 12; int types 6; // 圖案種類數(shù) int board[10][12]; // 實(shí)際使用時(shí)用 vectorvectorint判定函數(shù)是純內(nèi)存計(jì)算單次搜索在 10x10 的棋盤上耗時(shí)不到 1 毫秒。如果實(shí)測(cè)中發(fā)現(xiàn)點(diǎn)擊后有明顯卡頓優(yōu)先檢查是不是把整份棋盤拷貝傳參了傳引用能省掉大量復(fù)制開銷。另一個(gè)性能隱患是每次調(diào)用canConnect都重新分配三維vis數(shù)組這個(gè)可以接受但如果你要做“自動(dòng)提示”功能會(huì)頻繁調(diào)用數(shù)百次搜索那就要考慮復(fù)用內(nèi)存或者把vis改成整型時(shí)間戳標(biāo)記。4. 地圖生成與可解性保證隨機(jī)地圖不隨機(jī)洗牌邏輯要閉環(huán)4.1 生成合法地圖成對(duì)填充再洗牌連連看地圖生成的核心約束是每個(gè)圖案必須成對(duì)出現(xiàn)。最穩(wěn)妥的做法是先生成一個(gè)包含所有圖案對(duì)的一維數(shù)組隨機(jī)打亂后再填入棋盤。#include algorithm #include random #include vector using namespace std; // 生成棋盤rows*cols 必須是偶數(shù) vectorvectorint generateBoard(int rows, int cols, int types) { int total rows * cols; if (total % 2 ! 0) return {}; // 格子數(shù)必須為偶數(shù)才能成對(duì) // 每對(duì)圖案的編號(hào)為 i % types vectorint values; for (int i 0; i total / 2; i) { values.push_back(i % types); } // 復(fù)制一份保證每種圖案都有成對(duì)的另一半 vectorint all values; all.insert(all.end(), values.begin(), values.end()); // 隨機(jī)打亂 mt19937 rng(random_device{}()); shuffle(all.begin(), all.end(), rng); // 填入二維棋盤 vectorvectorint board(rows, vectorint(cols)); int idx 0; for (int i 0; i rows; i) { for (int j 0; j cols; j) { board[i][j] all[idx]; } } return board; }這里有個(gè)容易踩的坑如果直接for (int i 0; i total / 2; i) values.push_back(i % types)那么當(dāng)total / 2大于types時(shí)每種圖案會(huì)出現(xiàn)多對(duì)這沒問題但你需要保證total / 2能被types整除否則某些圖案會(huì)比其他圖案多一對(duì)消除到最后會(huì)剩下無法配對(duì)的格子。所以實(shí)際參數(shù)選擇時(shí)我會(huì)先算一下(rows * cols / 2) % types 0不滿足就把types調(diào)小或者把棋盤調(diào)大。4.2 可解性驗(yàn)證與自動(dòng)重排隨機(jī)生成的棋盤不能保證一定“有解”這里的“有解”指至少存在一對(duì)可消除的圖案。一個(gè)合格的開局應(yīng)該保證玩家第一步一定有可消除的對(duì)。最直接的做法是生成后跑一遍全棋盤掃描調(diào)用canConnect檢查是否存在任意一對(duì)相同圖案可消除。// 檢查當(dāng)前棋盤是否存在至少一對(duì)可消除的格子 bool hasValidMove(const vectorvectorint board) { int rows board.size(), cols board[0].size(); for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (board[i][j] 0) continue; for (int ii 0; ii rows; ii) { for (int jj 0; jj cols; jj) { if (i ii j jj) continue; if (board[i][j] ! board[ii][jj]) continue; if (canConnect(board, i, j, ii, jj)) return true; } } } } return false; } // 無解時(shí)重新洗牌 void shuffleBoard(vectorvectorint board) { int rows board.size(), cols board[0].size(); vectorint values; for (int i 0; i rows; i) for (int j 0; j cols; j) if (board[i][j] ! 0) values.push_back(board[i][j]); // 隨機(jī)打亂后填回非空格 mt19937 rng(random_device{}()); shuffle(values.begin(), values.end(), rng); int idx 0; for (int i 0; i rows; i) for (int j 0; j cols; j) if (board[i][j] ! 0) board[i][j] values[idx]; // 重排后仍然無解就繼續(xù)重排 if (!hasValidMove(board)) shuffleBoard(board); }這里的洗牌邏輯有個(gè)很玄學(xué)的現(xiàn)象隨機(jī)重排后有解的概率其實(shí)很高普通 10x10 棋盤配 6 種圖案無解概率大約只有百分之幾所以遞歸重排基本不會(huì)陷入死循環(huán)。但如果地圖參數(shù)設(shè)置得很極限比如 6x6 配 3 種圖案無解概率會(huì)急劇上升遞歸洗牌的深度可能變得不可控。我通常會(huì)在洗牌函數(shù)里加一個(gè)重試上限比如 20 次超過后就放寬參數(shù)重新生成避免極端情況下程序卡死。4.3 消除操作的主流程點(diǎn)擊、判定、更新地圖生成和判定函數(shù)都準(zhǔn)備好后游戲主邏輯就非常簡(jiǎn)單了。點(diǎn)擊第一個(gè)格子時(shí)記錄坐標(biāo)和圖案編號(hào)點(diǎn)擊第二個(gè)格子時(shí)調(diào)用canConnect返回 true 就把兩個(gè)格子置 0然后檢查是否勝負(fù)。這里要特別注意每次消除后棋盤發(fā)生變化之前“無解”的局面可能變“有解”因?yàn)榭崭褡兌嗔寺窂竭x擇更多。所以必須在每次消除后重新調(diào)用hasValidMove不是只在開局檢查一次。“死局檢測(cè)”和“洗牌按鈕”是實(shí)驗(yàn)報(bào)告里的加分項(xiàng)。我在實(shí)現(xiàn)時(shí)把這兩個(gè)功能綁定在一起每次消除后如果hasValidMove返回 false就彈出提示讓玩家選擇洗牌或者判定失敗。洗牌時(shí)只打亂剩余非空格不打亂已經(jīng)消除的空格否則棋盤會(huì)出現(xiàn)“虛空生成新圖案”的 bug。基于時(shí)間戳的vis復(fù)用技巧在這里能派上用場(chǎng)死局檢測(cè)需要遍歷所有格子對(duì)最壞情況要調(diào)用 O(n2) 次搜索如果每次都重新分配三維數(shù)組UI 線程會(huì)有明顯卡頓。5. 避坑連連看搜索里最容易翻車的五個(gè)細(xì)節(jié)5.1 終點(diǎn)格子被當(dāng)成障礙攔截現(xiàn)象兩個(gè)相鄰的相同圖案點(diǎn)擊后判定不可消除別的格子之間卻沒這個(gè)問題。原因BFS 的轉(zhuǎn)移條件里寫了if (board[nx][ny] ! 0) continue;放在終點(diǎn)判斷之前導(dǎo)致終點(diǎn)格本身是圖案被當(dāng)成障礙提前剪掉了。解決終點(diǎn)的判斷必須放在障礙判斷之前。我在前面代碼里已經(jīng)把nx ex ny ey的檢查放在board[nx][ny] ! 0之前順序不能反。這是連連看判定函數(shù)里最隱蔽也最常見的 bug排查方法是在canConnect入口打印起點(diǎn)終點(diǎn)的坐標(biāo)和圖案值。5.2 只記錄二維 visited導(dǎo)致錯(cuò)誤剪枝現(xiàn)象有些明明能消除的格子對(duì)搜索返回 false而且換一組格子又恢復(fù)正常。原因visited只記錄(x,y)坐標(biāo)同一格子先被某個(gè)方向訪問后其他方向到達(dá)該格子的狀態(tài)被丟棄。但不同方向進(jìn)入同一格子的后續(xù)路徑能力完全不同可能先到的那條路已經(jīng)用掉了 2 次拐彎另一條路還一次拐彎都沒用卻被錯(cuò)誤的“已訪問”標(biāo)記擋住。解決把visited改成三維vis[x][y][dir]保存每個(gè)方向獨(dú)立的最小拐彎次數(shù)。這是整個(gè)實(shí)驗(yàn)里最重要的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)點(diǎn)寫代碼之前先在草稿紙上畫一張 3x3 的棋盤模擬一遍狀態(tài)擴(kuò)展比直接寫代碼再調(diào)試快得多。5.3 起點(diǎn)和終點(diǎn)相同導(dǎo)致循環(huán)判斷現(xiàn)象玩家連續(xù)點(diǎn)擊同一個(gè)格子程序進(jìn)入死循環(huán)或者判定為“可消除”。原因起終點(diǎn)坐標(biāo)相同時(shí)BFS 的終點(diǎn)判斷會(huì)立刻命中但此時(shí)并沒有任何路徑屬于無效消除。解決函數(shù)入口直接加上if (sx ex sy ey) return false;。這個(gè)檢查看起來多余但沒有它點(diǎn)擊第二次同一個(gè)格子時(shí)會(huì)直接消除而且是零步“消除”嚴(yán)重破壞游戲規(guī)則。5.4 洗牌時(shí)把已消除的空格也打亂了現(xiàn)象點(diǎn)擊洗牌后棋盤上原本空著的位置出現(xiàn)了圖案而且總數(shù)不對(duì)。原因洗牌函數(shù)遍歷整個(gè)棋盤把所有格子都收進(jìn)數(shù)組包括值為 0 的空格打亂后空格也被填上了圖案。解決洗牌只收集非空格子。我上面的shuffleBoard里只把board[i][j] ! 0的值放進(jìn)數(shù)組重新填充時(shí)也跳過空格位置。這一點(diǎn)看起來是“低級(jí)錯(cuò)誤”但在邊界條件沒想清楚時(shí)很容易犯而且一旦出現(xiàn)對(duì)局?jǐn)?shù)據(jù)就徹底亂了。5.5 拐彎次數(shù)統(tǒng)計(jì)的起止偏差現(xiàn)象路徑明明拐了三次彎卻判定成功或者只拐了一次彎卻判定失敗。原因起點(diǎn)初始化時(shí)把四個(gè)方向的turns都設(shè)為 0這樣第一個(gè)格子直走到第二個(gè)格子時(shí)確實(shí)算 0 次拐彎但如果起點(diǎn)出發(fā)是斜著走的——雖然棋盤只有四方向斜走并不存在——這里的問題是終點(diǎn)相鄰時(shí)的拐彎計(jì)數(shù)從起點(diǎn)到終點(diǎn)如果直接到達(dá)沒有dir可比較有些實(shí)現(xiàn)會(huì)強(qiáng)行把這次移動(dòng)算成一次拐彎導(dǎo)致相鄰格子反而消除失敗。解決在起點(diǎn)初始化階段先檢查四個(gè)相鄰格子是否是終點(diǎn)是就直接返回 true把這個(gè)場(chǎng)景從 BFS 主流程中摘出去。終點(diǎn)相鄰不需要任何拐彎這是規(guī)則上的例外單獨(dú)處理比硬塞進(jìn)狀態(tài)轉(zhuǎn)移要干凈得多。6. 進(jìn)階雙向 BFS 加速自動(dòng)提示用路徑回溯做消除動(dòng)畫當(dāng)你把基礎(chǔ)判定函數(shù)跑通之后實(shí)驗(yàn)成績(jī)的上限取決于兩點(diǎn)自動(dòng)提示功能和消除動(dòng)畫。自動(dòng)提示的本質(zhì)是“找到任意一對(duì)可消除的格子”如果每次都用雙重循環(huán)嵌套canConnect10x10 棋盤最壞要跑幾百次搜索界面會(huì)卡到肉眼可見。我用的是雙向 BFS 的思路從起點(diǎn)和終點(diǎn)同時(shí)擴(kuò)展各自維護(hù)一套vis狀態(tài)當(dāng)兩個(gè)方向的擴(kuò)展區(qū)域相遇時(shí)說明找到一條連通路徑。雙向 BFS 對(duì)“拐彎次數(shù)”這類約束同樣適用只需要在狀態(tài)里同時(shí)記錄方向相遇時(shí)合并雙方的拐彎次數(shù)判斷總拐彎是否不超過 2。實(shí)現(xiàn)提示功能時(shí)有一個(gè)比雙向 BFS 更實(shí)用的技巧把“從某個(gè)點(diǎn)能走到的所有格子”預(yù)計(jì)算緩存下來。在棋盤開局和每次消除后遍歷所有非空格子以每個(gè)格子為起點(diǎn)跑一次 BFS記錄它能到達(dá)的所有同圖案格子結(jié)果存進(jìn)一個(gè)哈希表。后續(xù)調(diào)用提示時(shí)直接查表就能返回一組可消除對(duì)速度從 O(n2) 搜索降到 O(1) 查表。代價(jià)是每次棋盤變化后需要重建緩存但棋盤規(guī)模小重建一次也就幾十毫秒完全在可接受范圍內(nèi)。路徑回溯則是動(dòng)畫層的事。canConnect只返回布爾值但如果你想做“消除時(shí)高亮連線”需要額外的parent數(shù)組記錄每個(gè)狀態(tài)是從哪個(gè)狀態(tài)轉(zhuǎn)移過來的終點(diǎn)命中后再反向回溯得到完整路徑點(diǎn)列表。常見的做法是定義一個(gè)Node結(jié)構(gòu)體數(shù)組每個(gè)擴(kuò)展?fàn)顟B(tài)保存前驅(qū)下標(biāo)找到終點(diǎn)后用棧彈出路徑。在做界面輸出時(shí)把路徑中的拐點(diǎn)坐標(biāo)轉(zhuǎn)成折線繪制指令就能看到一條清晰的三段式連線。我做這個(gè)實(shí)驗(yàn)時(shí)最后一個(gè)教訓(xùn)是canConnect函數(shù)一定要保證“前后兩次調(diào)用之間不依賴任何全局狀態(tài)”。某次我圖省事把vis數(shù)組聲明成全局復(fù)用結(jié)果上一次搜索殘留的標(biāo)記污染了下一次判定查了大半天才發(fā)現(xiàn)是初始化沒清干凈。后來我強(qiáng)制要求自己每個(gè)搜索函數(shù)內(nèi)部自帶狀態(tài)初始化寧可多花幾次內(nèi)存分配也不碰全局復(fù)用。這個(gè)習(xí)慣后來在寫更復(fù)雜的圖搜索時(shí)幫了大忙。希望這篇能幫你在實(shí)驗(yàn)里少走幾步彎路把時(shí)間花在理解圖結(jié)構(gòu)本身而不是和詭異的 bug 較勁。本文還有配套的精品資源點(diǎn)擊獲取