做算法題這幾年有個(gè)很深的體會(huì)很多看起來“基礎(chǔ)”的題目其實(shí)才是最能拉開差距的地方。就拿東方博宜OJ上的1434題“數(shù)池塘四方向”來說單看名字平平無奇無非就是統(tǒng)計(jì)一個(gè)矩陣?yán)镉袔讐K水域但真正把它吃透你對(duì)Flood fill的理解、對(duì)DFS/BFS兩種寫法的掌握、對(duì)邊界條件的敏感度都會(huì)上一個(gè)臺(tái)階。這篇文章我想把這個(gè)題掰開了講從題意分析、兩種核心寫法的對(duì)比、四方向和八方向的區(qū)別到常見報(bào)錯(cuò)和調(diào)試技巧一次性說清楚。1. 題目拆解與核心思路1.1 題意到底在說什么先看題目本身。輸入是一個(gè)由字符組成的矩陣通常用W表示水坑Water.表示干地Land整個(gè)矩陣代表一片被劃分成方格的土地。題目要求統(tǒng)計(jì)共有多少個(gè)“池塘”而“池塘”的定義是上下左右四個(gè)方向上相鄰的W連成的一個(gè)連通塊。這點(diǎn)很關(guān)鍵。所謂的“四方向”指的是對(duì)一個(gè)格子而言只有上up、下down、左left、右right四個(gè)鄰居能被視為“同一片池塘”斜對(duì)角方向的W即使緊挨著也不算連在一起。很多新手第一次做這道題容易下意識(shí)把斜對(duì)角也算進(jìn)去那結(jié)果就會(huì)比正確答案多出不少連通塊。題目要求輸出的就是一個(gè)整數(shù)代表池塘的個(gè)數(shù)。數(shù)據(jù)范圍我印象中矩陣的行列都在100以內(nèi)規(guī)模不算大暴力深搜或者廣搜都能過但這道題真正的價(jià)值不在于“能不能跑完”而在于你有沒有把Flood fill的思路吃透。1.2 為什么暴力枚舉不可行有的同學(xué)可能會(huì)想那我直接雙重循環(huán)遍歷每個(gè)格子碰到W就把它周圍的W都標(biāo)記一下不就能統(tǒng)計(jì)出來了嗎這個(gè)想法方向沒錯(cuò)但問題在于“把周圍所有連通的W都標(biāo)記出來”這件事本身沒有那么簡(jiǎn)單。比如一個(gè)形狀像螺旋一樣的水域從左上角的W出發(fā)你如果不做遍歷只是單純看“上下左右有沒有W”那是沒辦法把一整片螺旋形池塘完整找出來的。更麻煩的是同一片池塘可能在遍歷過程中被重復(fù)計(jì)數(shù)比如你先從(0,0)這個(gè)W開始數(shù)了一次后面遍歷到(0,1)時(shí)發(fā)現(xiàn)它也是W如果不加判斷又把它當(dāng)成一個(gè)新池塘結(jié)果就錯(cuò)了。所以正確的思路必須是每遇到一個(gè)未被訪問過的W就把它所在的整個(gè)連通塊完整地“染色”一遍讓這片池塘里所有的W都變成“已訪問”狀態(tài)這樣后續(xù)遍歷再遇到它們時(shí)就不會(huì)重復(fù)計(jì)數(shù)。這個(gè)“染色”過程就是Flood fill算法的核心。2. Flood fill的兩種經(jīng)典實(shí)現(xiàn)2.1 DFS寫法遞歸的力量理解DFS深度優(yōu)先搜索的寫法關(guān)鍵要抓住三個(gè)要素當(dāng)前格子坐標(biāo)、訪問標(biāo)記、方向的擴(kuò)展。我先給出一個(gè)最典型的代碼模板后面再逐行解釋。#include iostream using namespace std; int n, m; char grid[105][105]; int visited[105][105]; // 四方向數(shù)組上、下、左、右 int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; void dfs(int x, int y) { visited[x][y] 1; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 nx n ny 0 ny m grid[nx][ny] W !visited[nx][ny]) { dfs(nx, ny); } } } int main() { cin n m; for (int i 0; i n; i) { for (int j 0; j m; j) { cin grid[i][j]; } } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] W !visited[i][j]) { ans; dfs(i, j); } } } cout ans endl; return 0; }這段代碼的核心邏輯其實(shí)只有兩個(gè)循環(huán)外層循環(huán)負(fù)責(zé)找到新池塘的起點(diǎn)內(nèi)層的dfs負(fù)責(zé)把整片池塘染色。我當(dāng)年第一次看這個(gè)題的時(shí)候始終想不明白一個(gè)問題“為什么主函數(shù)里每次碰到一個(gè)沒訪問過的W主動(dòng)ans之后調(diào)用dfs就能保證這個(gè)W和之前統(tǒng)計(jì)過的池塘不重疊”答案是所有之前已經(jīng)被統(tǒng)計(jì)過的池塘里面的每個(gè)W都會(huì)被標(biāo)記成visited 1所以主循環(huán)遍歷到它們的時(shí)候因?yàn)?visited[i][j]這個(gè)條件不成立根本就不會(huì)進(jìn)入ans分支。我想特別提醒一個(gè)初學(xué)者很容易犯的錯(cuò)有些同學(xué)會(huì)在dfs內(nèi)部也寫ans這基本必錯(cuò)。ans的計(jì)數(shù)應(yīng)該只發(fā)生在“發(fā)現(xiàn)了新連通塊起點(diǎn)”的那一刻等dfs擴(kuò)散完后這片池塘已經(jīng)被整體標(biāo)記了不能再被當(dāng)作新池塘。如果你在遞歸里計(jì)數(shù)那同一片池塘?xí)粩?shù)出很多次答案會(huì)變成一個(gè)很大的錯(cuò)誤數(shù)字。2.2 BFS寫法隊(duì)列的妙用BFS廣度優(yōu)先搜索寫法的思路和DFS本質(zhì)上是一樣的只不過“染色”的順序不同。DFS是一條路走到黑撞到邊界再回頭BFS則是像漣漪一樣一圈一圈向外擴(kuò)散。BFS需要用到隊(duì)列queue代碼長(zhǎng)一點(diǎn)但對(duì)某些場(chǎng)景更順手。#include iostream #include queue using namespace std; int n, m; char grid[105][105]; int visited[105][105]; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; void bfs(int x, int y) { queuepairint, int q; q.push({x, y}); visited[x][y] 1; while (!q.empty()) { int cx q.front().first; int cy q.front().second; q.pop(); for (int i 0; i 4; i) { int nx cx dx[i]; int ny cy dy[i]; if (nx 0 nx n ny 0 ny m grid[nx][ny] W !visited[nx][ny]) { visited[nx][ny] 1; q.push({nx, ny}); } } } } int main() { cin n m; for (int i 0; i n; i) { for (int j 0; j m; j) { cin grid[i][j]; } } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] W !visited[i][j]) { ans; bfs(i, j); } } } cout ans endl; return 0; }BFS寫法里有一個(gè)細(xì)節(jié)我反復(fù)跟人強(qiáng)調(diào)過在把鄰居節(jié)點(diǎn)加入隊(duì)列的那一刻就要立刻標(biāo)記visited而不是等它出隊(duì)時(shí)再標(biāo)記。為什么因?yàn)槿绻涣⒖虡?biāo)記同一個(gè)格子可能被多個(gè)方向同時(shí)發(fā)現(xiàn)然后被重復(fù)加入隊(duì)列。雖然這不會(huì)導(dǎo)致答案錯(cuò)誤但會(huì)導(dǎo)致隊(duì)列里多出大量重復(fù)元素在矩陣規(guī)模大的時(shí)候明顯拖慢速度嚴(yán)重的還可能造成超時(shí)。2.3 兩種寫法該怎么選說實(shí)話對(duì)于數(shù)池塘這道題的數(shù)據(jù)范圍DFS和BFS在效率上沒有本質(zhì)區(qū)別選哪種全看你個(gè)人的熟練度。但我個(gè)人的經(jīng)驗(yàn)是如果你剛學(xué)Flood fill請(qǐng)先死磕BFS寫法。理由很簡(jiǎn)單DFS雖然代碼短但它的遞歸調(diào)用在迷宮規(guī)模極大比如1000x1000的矩陣都是W時(shí)可能因?yàn)檫f歸層數(shù)太深導(dǎo)致爆棧。很多OJ上的題目數(shù)據(jù)范圍看著不大但出題人可能會(huì)在同題異構(gòu)的進(jìn)階版本里偷偷把范圍拉大這時(shí)候DFS直接運(yùn)行報(bào)錯(cuò)你還得額外改成棧模擬BFS就沒有這個(gè)問題。此外BFS天然帶有“距離由近到遠(yuǎn)”的性質(zhì)將來遇到要統(tǒng)計(jì)連通塊大小、求最短步數(shù)這類題目時(shí)隊(duì)列里的數(shù)據(jù)天然分層改起來很順手。DFS則更適合在需要輸出具體路徑、或者回溯剪枝的場(chǎng)景中用。早點(diǎn)把兩種寫法都練熟日后遇到題目就能根據(jù)需求靈活切換。3. 四方向與八方向差之一字謬之千里3.1 方向數(shù)組到底在表達(dá)什么很多初學(xué)者誤以為四方向只是把dx、dy數(shù)組從4個(gè)元素改成8個(gè)元素那么簡(jiǎn)單。對(duì)也不對(duì)。改方向數(shù)組的確是最直觀的一步但背后涉及的是邏輯上對(duì)“連通性”定義的根本改變。先看四方向的方向定義。如果你把矩陣想象成一張地圖坐標(biāo)軸是x行、y列那么四方向?qū)?yīng)的偏移量就是方向dx行偏移dy列偏移上-10下10左0-1右01注意這里x減一是“向上”走x加一是“向下”走和我們?cè)谥苯亲鴺?biāo)系里的習(xí)慣正好相反。因?yàn)槎S數(shù)組的第一維度行號(hào)是自上而下增長(zhǎng)的。這個(gè)點(diǎn)如果沒想清楚寫代碼時(shí)很容易把上下方向搞反雖然對(duì)最終答案可能沒影響四個(gè)方向都遍歷了但解題幸福感會(huì)大打折扣。八方向相對(duì)就復(fù)雜一些除了上下左右還要加入左上、右上、左下、右下四個(gè)斜向。方向數(shù)組變成int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1};四方向中坐標(biāo)(0,0)和(1,1)雖然在對(duì)角線上緊挨著但它們不算連通在八方向中它們就是同一個(gè)連通塊。3.2 實(shí)戰(zhàn)中如何確認(rèn)題目要哪種這看起來是個(gè)很簡(jiǎn)單的問題但在東方博宜OJ上同一個(gè)“數(shù)池塘”題目其實(shí)有兩個(gè)版本一個(gè)要求四方向一個(gè)要求八方向。如果你拿四方向的代碼去交八方向的題結(jié)果大概率是答案偏大因?yàn)楸驹撨B成一片的池塘被你拆成了多塊反過來如果你拿八方向的模板去交四方向的題答案就偏小因?yàn)槎鄠€(gè)不同的池塘被錯(cuò)誤地合并成了一片。我強(qiáng)烈建議拿到任何搜索題第一步不是急著寫代碼而是把題目里的“相鄰”定義圈出來。題目里寫“上下左右”就是四方向?qū)憽鞍藗€(gè)方向”或“周圍八格”就是八方向。有時(shí)候題目還會(huì)表述成“只能水平或垂直移動(dòng)”這時(shí)候也必然是四方向?？辞孱}目再動(dòng)手能省掉后面一整輪的排查時(shí)間。3.3 方向順序會(huì)影響答案和效率嗎對(duì)答案不會(huì)對(duì)運(yùn)行效率可能有微妙影響但通?？梢院雎?。DFS遞歸時(shí)四個(gè)方向的搜索順序在邏輯上等價(jià)因?yàn)樽罱K都會(huì)遍歷完同一個(gè)連通塊。唯一可能產(chǎn)生差別的是遞歸棧的深度軌跡在極端地形下某個(gè)方向優(yōu)先會(huì)先碰到底但這對(duì)現(xiàn)代計(jì)算機(jī)來說微不足道。不過有一個(gè)例外如果題目要求輸出連通塊內(nèi)格子坐標(biāo)的某種順序比如按字典序那方向數(shù)組的順序就需要刻意設(shè)計(jì)了。數(shù)池塘這道題沒有這種要求所以你可以按舒服的順序?qū)?。我自己?xí)慣按上、下、左、右排和很多教材保持一致方便記憶不易在比賽中手滑寫錯(cuò)。4. 邊界處理與visited標(biāo)記的深層邏輯4.1 越界檢查為什么必須放在最前面新手寫DFS/BFS時(shí)最容易出的問題就是在遞歸函數(shù)里訪問了不存在的格子坐標(biāo)程序直接在運(yùn)行期報(bào)段錯(cuò)誤segmentation fault。比如當(dāng)前點(diǎn)在(0,0)你往上走變成(-1,0)這時(shí)候如果直接訪問grid[-1][0]數(shù)組下標(biāo)越界行為是未定義的。常見的誤區(qū)是把越界檢查放在grid[nx][ny] W之后。比如有人會(huì)這樣寫if (grid[nx][ny] W nx 0 nx n ny 0 ny m !visited[nx][ny])這種寫法是錯(cuò)的因?yàn)镃在計(jì)算表達(dá)式時(shí)是從左到右依次求值的一旦grid[nx][ny]先被訪問而nx已經(jīng)越界程序已經(jīng)出錯(cuò)了。必須保證邊界檢查永遠(yuǎn)最先執(zhí)行if (nx 0 nx n ny 0 ny m grid[nx][ny] W !visited[nx][ny])你可以把理解為“關(guān)卡”越界檢查是第一道關(guān)字符判斷是第二道關(guān)訪問標(biāo)記是第三道關(guān)。順序錯(cuò)了后面兩關(guān)形同虛設(shè)。4.2 能否原地修改grid代替visited數(shù)組代碼里能省則省是很多選手的追求有同學(xué)會(huì)想既然要標(biāo)記已訪問那直接把這個(gè)格子從W改成.不就行了嗎確實(shí)可以實(shí)際上很多工整的題解就是這么干的。這種做法在競(jìng)賽中很常見還能省掉一個(gè)數(shù)組的內(nèi)存空間。void dfs(int x, int y) { grid[x][y] .; // 直接把水坑改成陸地相當(dāng)于標(biāo)記已訪問 for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 nx n ny 0 ny m grid[nx][ny] W) { dfs(nx, ny); } } }我個(gè)人建議初學(xué)階段老老實(shí)實(shí)用visited數(shù)組。原因有二。第一調(diào)試的時(shí)候你還能看到原始地圖長(zhǎng)什么樣方便你肉眼追蹤搜索過程如果直接把grid改了調(diào)試時(shí)一片模糊。第二有的進(jìn)階題目后續(xù)還需要用原圖做別的計(jì)算你提前破壞了原始數(shù)據(jù)會(huì)陷入被動(dòng)。等你對(duì)Flood fill完全駕輕就熟再考慮空間優(yōu)化不遲。4.3 連通塊遍歷的終止條件什么時(shí)候算“這一片池塘找完了”從算法角度來說就是當(dāng)隊(duì)列為空BFS或遞歸自然返回DFS時(shí)。遞歸的自然返回沒有顯式的return是因?yàn)楹瘮?shù)體執(zhí)行完就自動(dòng)返回了。每一個(gè)格子都被訪問過它的四個(gè)方向要么越界、要么不是水、要么已被標(biāo)記沒有新的可擴(kuò)展點(diǎn)遞歸就層層退出。這里有個(gè)小技巧如果你在遞歸函數(shù)末尾打印一下當(dāng)前坐標(biāo)和走向就能很直觀地看到搜索軌跡。我在本地調(diào)試時(shí)特別喜歡加一句cout visiting: x , y endl;看幾組數(shù)據(jù)之后對(duì)遞歸的順序感受完全不同。做題不光為了AC更為了真正理解?；ㄊ昼娪^察這個(gè)過程比刷十道題更值。5. 完整提交流程與細(xì)節(jié)優(yōu)化5.1 從讀入到輸出的完整流程這道題的輸入格式通常是第一行兩個(gè)整數(shù)n和m表示行數(shù)和列數(shù)接下來n行每行m個(gè)字符中間沒有空格。讀入的時(shí)候用cin grid[i][j]即可自動(dòng)跳過空白字符。完整流程可以總結(jié)成四步讀入矩陣的尺寸和內(nèi)容。初始化visited為0全局?jǐn)?shù)組默認(rèn)已是0但顯式重置更穩(wěn)妥。雙重循環(huán)遍歷每個(gè)格子遇到未訪問的W就計(jì)數(shù)并調(diào)用搜索函數(shù)。輸出總數(shù)。我見過一個(gè)坑是有人把n和m讀反了導(dǎo)致雙重循環(huán)越界或者遍歷范圍不夠。題目里如果明確寫了“n代表行m代表列”就老老實(shí)實(shí)按這個(gè)來不要想當(dāng)然認(rèn)為第一個(gè)數(shù)字一定是行。養(yǎng)成讀入后看一眼實(shí)際數(shù)據(jù)的習(xí)慣能幫你避開這種低級(jí)失誤。5.2 使用全局?jǐn)?shù)組的好處做題時(shí)我傾向于把所有數(shù)組和遞歸函數(shù)都定義在全局作用域而不是main函數(shù)內(nèi)部。為什么第一全局?jǐn)?shù)組默認(rèn)自動(dòng)初始化為0省去memset的工作第二dfs遞歸函數(shù)訪問全局變量不需要通過參數(shù)傳遞矩陣和標(biāo)記數(shù)組函數(shù)簽名簡(jiǎn)潔很多出錯(cuò)率低第三全局?jǐn)?shù)組開在靜態(tài)區(qū)不會(huì)因?yàn)闂？臻g不足而崩潰。放到main內(nèi)部定義數(shù)組當(dāng)然也可以但局部數(shù)組存儲(chǔ)在棧上極端情況下大數(shù)組可能導(dǎo)致棧溢出。雖然本題100x100的規(guī)模遠(yuǎn)不至于但從一開始養(yǎng)成好習(xí)慣后面遇到更大規(guī)模的題目就不慌。我還習(xí)慣為數(shù)組多留一點(diǎn)余量比如題目說最多100我就開105寧可多幾行內(nèi)存不給越界留機(jī)會(huì)。5.3 代碼風(fēng)格與可讀性建議競(jìng)賽博主有時(shí)候喜歡把代碼壓到最短但我不推薦初學(xué)者追求這個(gè)。我自己的習(xí)慣是變量名盡量有意義grid就是地圖visited就是訪問標(biāo)記dfs、bfs就是函數(shù)名一眼看懂。方向數(shù)組固定命名為dx和dy這也是社區(qū)通用命名寫比賽時(shí)能減少思考成本。在東方博宜OJ這類在線評(píng)測(cè)平臺(tái)上提交編譯環(huán)境通常是C17上面的代碼直接就能通過。如果你的編譯器提示pair找不到記得包含utility頭文件不過通常iostream和queue已經(jīng)間接包含了問題不大。還是那句話與其糾結(jié)這些細(xì)枝末節(jié)不如把時(shí)間花在理解算法上。6. 常見錯(cuò)誤與調(diào)試技巧實(shí)錄6.1 答案偏大的原因分析用四方向代碼做完題如果你的輸出比正確答案大優(yōu)先檢查以下三處。visited標(biāo)記遺漏。有些格子明明屬于同一片池塘但因?yàn)闃?biāo)記條件寫錯(cuò)導(dǎo)致被重復(fù)計(jì)數(shù)。方向數(shù)組寫錯(cuò)。比如把四方向的dx、dy誤填成八方向的長(zhǎng)度導(dǎo)致本該連通的格子沒走通。遞歸入口條件放寬。比如判斷grid[nx][ny] W時(shí)沒有加上!visited[nx][ny]但這反而會(huì)導(dǎo)致重復(fù)入隊(duì)答案偏大的概率反而較低最典型的還是前面說的在遞歸里計(jì)數(shù)。6.2 答案偏小的原因分析答案偏小則通常是過度合并了池塘。最常見的情況是用八方向代碼去做四方向的題。斜對(duì)角的水域被錯(cuò)誤地并入了同一塊池塘個(gè)數(shù)自然變少。還有就是邊界處理時(shí)某些W被錯(cuò)誤地改成了.或visited被錯(cuò)誤標(biāo)記為1導(dǎo)致本應(yīng)獨(dú)立的連通塊沒被計(jì)數(shù)。這類問題最難查因?yàn)榇a邏輯看著沒問題只有在你用一個(gè)小規(guī)模樣例手工模擬時(shí)才能發(fā)現(xiàn)。6.3 兩個(gè)經(jīng)典小樣例幫你驗(yàn)證代碼我每次寫完Flood fill類題目都會(huì)先用下面這些小樣例驗(yàn)證一遍。樣例一單塊小池塘3 3 W.. .W. ..W對(duì)角線上有三個(gè)W但四方向規(guī)則下它們互不相鄰應(yīng)該輸出3。樣例二兩塊獨(dú)立的池塘3 4 WW.. ..WW .....第一行WW是一塊第二行WW是另一塊輸出2。如果把兩個(gè)WW放成對(duì)角線相鄰四方向依然是2八方向就會(huì)變成1。跑通這兩個(gè)樣例你的核心邏輯基本就穩(wěn)了。調(diào)試時(shí)還可以故意加大矩陣尺寸比如100行100列全部填W看程序是否能在幾百毫秒內(nèi)跑完。這能驗(yàn)證代碼在極端全連通情況下的效率和遞歸深度是否安全。6.4 我的本地調(diào)試小工具我想分享一個(gè)比較個(gè)人化的習(xí)慣本地調(diào)試時(shí)我會(huì)在搜索前后分別打印矩陣標(biāo)記被訪問的格子。簡(jiǎn)單做法是在遞歸函數(shù)開頭臨時(shí)加一行把當(dāng)前格子改成小寫字母或數(shù)字這樣在終端里能清晰看到“染色”的過程。void dfs(int x, int y) { grid[x][y] *; // 臨時(shí)標(biāo)記方便觀察 // ... }注意交題之前一定記得把這些調(diào)試代碼刪掉或者用#ifdef LOCAL之類的宏包起來不然輸出格式會(huì)被破壞評(píng)測(cè)直接判WA。我當(dāng)年就干過這種蠢事本地跑得好好的一提交全錯(cuò)檢查半小時(shí)發(fā)現(xiàn)是調(diào)試輸出混進(jìn)了結(jié)果里。從那以后我寫任何題目都養(yǎng)成“提交前通讀一遍主輸出邏輯”的習(xí)慣。7. 從數(shù)池塘到更廣闊的搜索世界7.1 同類型題目的一通百通數(shù)池塘這道題看似簡(jiǎn)單但它其實(shí)是無數(shù)經(jīng)典搜索題的“內(nèi)核”。最典型的就是LeetCode上的“島嶼數(shù)量”問題給的矩陣由1和0組成讓你統(tǒng)計(jì)島嶼個(gè)數(shù)本質(zhì)上就是統(tǒng)計(jì)四方向連通塊的數(shù)量。你再想遠(yuǎn)一點(diǎn)圖像處理里的“連通區(qū)域標(biāo)記”算法、掃地機(jī)器人做區(qū)域覆蓋時(shí)的地圖分割、迷宮尋路里的可達(dá)性判斷底層全都是這一套Flood fill思想。我建議做完1434題之后順手把以下幾類變體都練一遍統(tǒng)計(jì)每個(gè)連通塊的大小在DFS/BFS里加一個(gè)計(jì)數(shù)器。找出最大的連通塊。判斷一個(gè)特定坐標(biāo)所在的連通塊包含哪些格子。改造為八方向版本。這些變體每改一個(gè)條件你對(duì)這道題的掌握就深一層。等到下次在比賽中遇到陌生題目你就會(huì)條件反射地想“這不就是Flood fill的換皮版本嗎”7.2 進(jìn)階路徑壓縮用并查集如果說Flood fill是“連續(xù)染色”的思路那并查集則是“按需合并”的思路。你可以把每個(gè)W都看作一個(gè)孤立節(jié)點(diǎn)然后檢查相鄰的W把它們合并到同一個(gè)集合里。最后統(tǒng)計(jì)有多少個(gè)集合就是池塘數(shù)。兩種方法的時(shí)間和空間復(fù)雜度在本題量級(jí)下相差不大但并查集在一些特殊場(chǎng)景下更靈活。比如題目中途可能會(huì)修改地圖上某個(gè)格子的狀態(tài)或者需要?jiǎng)討B(tài)詢問兩個(gè)格子是否連通這時(shí)候Flood fill每次都要重跑一遍并查集卻可以增量更新。當(dāng)然這是后話就數(shù)池塘這道題而言Flood fill是最直觀、最好寫、最不易錯(cuò)的方案。7.3 我對(duì)數(shù)池塘這道題的整體評(píng)價(jià)東方博宜OJ把這道題放在基礎(chǔ)位置是有道理的。它沒有復(fù)雜的數(shù)學(xué)變形沒有刁鉆的邊界條件連“四方向”都在題目名字里明明白白寫好了。但它恰恰能讓老師一眼看出你是不是真正理解了搜索的精髓標(biāo)記狀態(tài)、遍歷鄰居、避免重復(fù)計(jì)數(shù)。這三個(gè)詞聽起來簡(jiǎn)單能做到不犯錯(cuò)全靠大量練習(xí)堆積。我自己帶過一些學(xué)弟學(xué)妹有人一眼就會(huì)寫有人看題解恍然大悟但過兩周再遇到類似題又卡住了。差別就在于有沒有真的跑過樣例、畫過遞歸流程、親手調(diào)試過某個(gè)困住自己的錯(cuò)誤。所以我還是那句話別看這道題簡(jiǎn)單務(wù)必親手提交一次務(wù)必親手造幾個(gè)樣例驗(yàn)證它。8. 一些實(shí)戰(zhàn)中的個(gè)人心得最后還想再多說幾句關(guān)于解題心態(tài)的話。數(shù)池塘這類Flood fill題目是少有的“能做對(duì)很容易、能做快也不難、但做得好需要積累”的題型。你不需要掌握什么高深的優(yōu)化技巧只要抱著樸素的想法——把每片池塘都“淹沒”一遍——代碼自然就寫出來了。有幾個(gè)可以提高解題速度的小習(xí)慣我很受用。寫方向數(shù)組時(shí)永遠(yuǎn)先想清楚dx和dy的對(duì)應(yīng)關(guān)系再動(dòng)手盡量在紙上勾勒出矩陣的坐標(biāo)軸把“上減下加左減右加”這種口號(hào)背熟能省不少心。再比如所有搜索題的入口判斷一定要簡(jiǎn)單統(tǒng)一我習(xí)慣用“當(dāng)前格子未訪問且滿足題目條件”其他特殊情況一律交給遞歸內(nèi)部處理?；氐?434這道題本身四方向Flood fill只是第一步我知道好多同學(xué)是做完它才真正分清DFS和BFS的適用場(chǎng)景的。如果你能順著這個(gè)思路把“數(shù)池塘”這個(gè)系列的每一道變體都吃透那你的圖論搜索基礎(chǔ)就算是真正夯實(shí)了。以后再遇到什么迷宮、掃雷、棋盤染色之類的問題都會(huì)感覺格外親切因?yàn)樗鼈兊膬?nèi)核早在你做這道“簡(jiǎn)單”題時(shí)就已經(jīng)埋下了。