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