1. 問題重述與核心思路拆解“擴散”這道題是2020年藍(lán)橋杯國賽C B組的一道經(jīng)典題目。很多初次接觸的同學(xué)看到“擴散”二字可能會聯(lián)想到物理現(xiàn)象或者圖像處理但在這道題里它被抽象成了一個非常典型的計算幾何與圖論搜索相結(jié)合的問題。我們先拋開代碼用最直白的話把題目意思和我們要做的事情講清楚。想象一個無限大的網(wǎng)格紙每一個格子用一個整數(shù)坐標(biāo)(x, y)來表示。最開始有四個點被“感染”了或者說被“點亮”了。題目告訴我們每一分鐘每一個已被感染的點會向它的上、下、左、右四個相鄰的格子即曼哈頓距離為1的格子擴散感染。一個新格子被感染后在下一分鐘也會加入擴散的行列。我們的目標(biāo)很簡單計算出在第2020分鐘結(jié)束時或者說從第0分鐘開始經(jīng)過2020分鐘后有多少個格子被感染了。這聽起來是不是有點像“細(xì)胞分裂”或者“病毒傳播”沒錯其本質(zhì)就是一個在離散網(wǎng)格上的傳播過程。最直接的思路就是模擬我們有一個集合來存放所有已被感染的點每分鐘遍歷這個集合把每個點的四個鄰居加入集合直到時間到2020分鐘最后統(tǒng)計集合的大小。但是這里有一個巨大的陷阱。如果真去模擬一個無限大的平面哪怕只模擬2020分鐘感染范圍也會是一個邊長超過4000的巨大正方形區(qū)域點數(shù)量級在千萬以上。在比賽環(huán)境下無論是時間還是內(nèi)存直接進(jìn)行BFS廣度優(yōu)先搜索模擬都是不可行的。我們必須找到更巧妙的方法。這道題的精髓就在于它考察你是否能跳出“模擬”的慣性思維轉(zhuǎn)而利用曼哈頓距離和離散幾何的性質(zhì)將問題轉(zhuǎn)化為一個判斷點是否可達(dá)的數(shù)學(xué)問題。核心思路如下任何一個坐標(biāo)點(x, y)如果它能被初始的某個感染點(x0, y0)在2020分鐘內(nèi)“擴散”到那么它們之間的曼哈頓距離必須滿足|x - x0| |y - y0| 2020。曼哈頓距離也叫出租車距離就是兩點在標(biāo)準(zhǔn)坐標(biāo)系上的絕對軸距之和。為什么是這個條件因為每分鐘擴散一步每一步只能改變一個坐標(biāo)值1個單位上/下/左/右。所以從(x0, y0)走到(x, y)最短路徑就是曼哈頓距離。如果這個最短距離都超過了2020那肯定無法在2020步內(nèi)到達(dá)。因此問題瞬間簡化了我們不需要模擬過程只需要枚舉一個有限區(qū)域內(nèi)的所有整數(shù)點然后判斷這個點是否至少與一個初始感染點的曼哈頓距離 2020。如果是則該點被感染。接下來的關(guān)鍵就是這個需要枚舉的“有限區(qū)域”有多大我們不能枚舉無限平面但我們可以確定一個邊界框。由于初始點坐標(biāo)是(0,0), (2020,11), (11,14), (2000,2000)擴散范圍是2020那么所有可能被感染的點其坐標(biāo)一定滿足min_x - 2020 x max_x 2020min_y - 2020 y max_y 2020其中min_x, max_x是四個初始點x坐標(biāo)的最小最大值y坐標(biāo)同理。計算一下x坐標(biāo)最小是0最大是2000y坐標(biāo)最小是0最大是2000。所以枚舉范圍大約是x ∈ [-2020, 4020],y ∈ [-2020, 4020]。這個區(qū)域大約是6000*60003600萬個點。對于每個點我們需要計算它與4個初始點的曼哈頓距離。3600萬 * 4 約1.44億次距離計算。每次計算就是兩次絕對值加法這是一個常數(shù)級別的操作。在C中1.44億次簡單運算是完全可以在1秒內(nèi)完成的通常現(xiàn)代CPU每秒可進(jìn)行數(shù)十億次運算。因此枚舉判斷法是此題的可行且高效的解決方案。2. 曼哈頓距離與BFS算法的本質(zhì)聯(lián)系在深入代碼之前我們有必要厘清曼哈頓距離判斷法和BFS模擬法之間的深層聯(lián)系。這能幫助我們理解為什么前者能替代后者以及在什么情況下它們等價。BFS廣度優(yōu)先搜索模擬是從源點一層層向外“漣漪式”地探索。在第0分鐘只有初始點。第1分鐘是所有初始點的曼哈頓距離為1的點。第2分鐘是所有曼哈頓距離為2的點且未被之前感染的點…… 以此類推。BFS天然地按照曼哈頓距離的層次來遍歷節(jié)點。在無障礙物的無限網(wǎng)格上本題正是如此從單源點(x0, y0)進(jìn)行BFS第t分鐘或第t步訪問到的所有新節(jié)點恰好就是所有滿足曼哈頓距離 t的節(jié)點。而t分鐘內(nèi)能訪問到的所有節(jié)點的集合就是所有滿足曼哈頓距離 t的節(jié)點。這是一個非常重要的性質(zhì)。它意味著在這種理想網(wǎng)格上BFS的“前沿”就是一個以源點為中心的菱形或者說旋轉(zhuǎn)了45度的正方形。這個菱形上的所有點到源點的曼哈頓距離相等。對于多源點BFS本題有4個初始感染點情況類似。任何一個點(x, y)只要它到任意一個源點的曼哈頓距離 t那么它一定會在t分鐘內(nèi)被感染。因為多源BFS可以看作是同時從多個源點開始的BFS每個點被感染的時間等于它到所有源點的曼哈頓距離的最小值。因此min_distance_to_any_source(x, y) 2020這個判斷條件完全等價于對這個多點系統(tǒng)進(jìn)行2020分鐘的BFS模擬后該點是否被訪問到的結(jié)果。這就是我們能用數(shù)學(xué)計算替代模擬過程的理論基礎(chǔ)。思考如果題目中的擴散規(guī)則變了比如每分鐘可以走“斜角”像國際象棋里的國王那么最短距離就變成了切比雪夫距離max(|x-x0|, |y-y0|)。判斷條件也要相應(yīng)改變。所以理解“距離”的定義如何由“移動規(guī)則”決定是解決這類擴散/傳播問題的關(guān)鍵。3. 從暴力枚舉到代碼實現(xiàn)理論清晰了現(xiàn)在我們來動手實現(xiàn)。我們將采用最直接的枚舉判斷法。代碼結(jié)構(gòu)非常清晰定義初始點將四個初始感染點存入一個數(shù)組或向量。確定枚舉邊界計算所有初始點x和y坐標(biāo)的最大最小值然后分別減去和加上擴散時間2020得到我們要枚舉的x和y的范圍。雙重循環(huán)枚舉遍歷邊界范圍內(nèi)的每一個整數(shù)坐標(biāo)(i, j)。判斷感染對于每個(i, j)計算它到四個初始點的曼哈頓距離。如果有一個距離 2020則計數(shù)器加1。輸出結(jié)果循環(huán)結(jié)束后計數(shù)器中的值就是答案。這里有一個極其重要的細(xì)節(jié)初始的四個點本身在第0分鐘就已經(jīng)被感染了。在我們的判斷條件距離 2020中它們到自身的距離是0顯然滿足條件所以會被自然計數(shù)在內(nèi)。我們不需要單獨處理。讓我們來看核心代碼實現(xiàn)#include iostream #include vector #include cmath // 用于abs函數(shù)但也可以自己實現(xiàn) using namespace std; // 定義點的結(jié)構(gòu)體 struct Point { int x, y; Point(int _x, int _y) : x(_x), y(_y) {} }; int main() { // 1. 初始化四個源點 vectorPoint sources; sources.emplace_back(0, 0); sources.emplace_back(2020, 11); sources.emplace_back(11, 14); sources.emplace_back(2000, 2000); int time_limit 2020; int cnt 0; // 感染點計數(shù)器 // 2. 計算枚舉的邊界 int min_x 0, max_x 2000; // 已知的初始點坐標(biāo)范圍 int min_y 0, max_y 2000; // 實際上我們需要根據(jù)初始點動態(tài)計算這里直接寫出已知值。更通用的寫法是遍歷sources數(shù)組求最值。 // int min_x sources[0].x, max_x sources[0].x; // int min_y sources[0].y, max_y sources[0].y; // for (const auto p : sources) { // min_x min(min_x, p.x); max_x max(max_x, p.x); // min_y min(min_y, p.y); max_y max(max_y, p.y); // } int start_x min_x - time_limit; int end_x max_x time_limit; int start_y min_y - time_limit; int end_y max_y time_limit; // 3. 雙重循環(huán)枚舉所有點 for (int x start_x; x end_x; x) { for (int y start_y; y end_y; y) { // 4. 判斷當(dāng)前點(x,y)是否能在time_limit內(nèi)被任一源點感染 bool infected false; for (const auto source : sources) { int distance abs(x - source.x) abs(y - source.y); if (distance time_limit) { infected true; break; // 找到一個可達(dá)源點就跳出內(nèi)層循環(huán) } } if (infected) { cnt; } } } // 5. 輸出結(jié)果 cout cnt endl; return 0; }這段代碼邏輯正確但我們可以做一些優(yōu)化和補充說明邊界計算代碼中我注釋掉了動態(tài)計算邊界的部分直接用了已知值。在正式解題時建議使用動態(tài)計算這樣即使初始點改變代碼也無需修改。abs()函數(shù)計算曼哈頓距離需要用到絕對值。cmath或cstdlib中的abs()函數(shù)對整數(shù)是有效的。也可以自己寫一個int d (x source.x) ? (x - source.x) : (source.x - x);但使用標(biāo)準(zhǔn)庫函數(shù)更簡潔。循環(huán)優(yōu)化對于最內(nèi)層循環(huán)要判斷4個源點我們采用了break提前退出。這是一個小的優(yōu)化。因為一旦發(fā)現(xiàn)某個點可達(dá)就沒必要再計算它到其他源點的距離了。時間復(fù)雜度如前所述枚舉點數(shù)量約(40002020*2)^2 ≈ 6000^2 36M每個點最多4次距離計算總共約1.44億次操作在競賽的1秒/2秒時限內(nèi)是可行的。運行這段代碼你會得到最終的答案。這里我不直接寫出答案希望你能夠自己運行并驗證。4. 算法優(yōu)化與邊界情況探討雖然枚舉法已經(jīng)可以解決問題但我們還可以思考一下有無優(yōu)化空間以及一些特殊的邊界情況。優(yōu)化思路減少枚舉量我們枚舉了一個矩形區(qū)域但實際感染點分布在一個類似“四個菱形并集”的形狀里。矩形的四個角有很大一片區(qū)域是絕對不可能被感染的距離所有源點都太遠(yuǎn)。有沒有辦法只枚舉可能的區(qū)域呢一個思路是對于每個源點感染區(qū)域是一個菱形。我們可以枚舉每個源點對應(yīng)的菱形區(qū)域然后取這些區(qū)域的并集。但計算并集本身比較麻煩可能需要使用掃描線或者更復(fù)雜的幾何計算其編程復(fù)雜度遠(yuǎn)高于簡單的矩形枚舉。在競賽中“矩形枚舉距離判斷”在實現(xiàn)速度和思維難度上取得了最佳平衡是最推薦的做法。另一種思路是只枚舉y軸方向然后對于每個y計算x的取值范圍。因為對于一個給定的y到某個固定源點(x0, y0)曼哈頓距離 T的點其x坐標(biāo)必須滿足|x - x0| T - |y - y0|。即x0 - (T - |y-y0|) x x0 (T - |y-y0|)。對于多個源點x的取值范圍就是這些區(qū)間的并集。我們可以遍歷y然后計算每個y對應(yīng)的x區(qū)間并集的總長度最后求和。這種方法可以將復(fù)雜度從O(N^2)降到O(N * K)其中N是坐標(biāo)范圍K是源點數(shù)量這里K4。實現(xiàn)起來比雙重循環(huán)稍復(fù)雜但效率更高。不過對于本題規(guī)模雙重循環(huán)足矣。邊界情況與易錯點坐標(biāo)范圍與整數(shù)溢出本題坐標(biāo)和擴散時間都在2000左右加減后范圍在-2020到4020之間用int類型完全足夠不會溢出。時間從0開始第0分鐘已經(jīng)有4個點。我們的算法中距離2020的點包含了第0到第2020分鐘所有被感染的點計算是正確的。如果題目問“第2020分鐘結(jié)束后”或者“經(jīng)過2020分鐘后”通常都包括初始狀態(tài)。源點重復(fù)題目保證了源點不重復(fù)。如果源點重復(fù)我們的算法依然正確因為重復(fù)判斷并不會增加計數(shù)一個點不會被重復(fù)感染。答案的表示最終答案是一個整數(shù)可能比較大百萬級別用int或long long存儲均可。踩坑實錄我最初實現(xiàn)時曾想當(dāng)然地認(rèn)為感染區(qū)域是一個大矩形于是嘗試計算矩形面積。但很快發(fā)現(xiàn)四個菱形區(qū)域的并集并不是一個簡單的矩形它的邊界是凹凸不平的。直接計算面積會漏掉一些凹進(jìn)去的格子也會多算一些凸出來的角。這個錯誤讓我意識到在離散網(wǎng)格上基于曼哈頓距離的形狀其面積不能直接用連續(xù)幾何的公式計算必須通過離散點的枚舉來精確計數(shù)。這是此類題目一個經(jīng)典的思維陷阱。5. 從“擴散”到更廣泛的搜索問題解決這道“擴散”題我們掌握的核心武器是將BFS的“過程模擬”問題轉(zhuǎn)化為基于“距離”的“狀態(tài)判斷”問題。這個思想可以推廣到許多類似場景多源點BFS最短路徑在一個無權(quán)圖中或網(wǎng)格中求所有點到一組起點的最近距離。可以直接初始化所有起點距離為0然后一次性放入隊列進(jìn)行BFS。這本質(zhì)上就是多源擴散。障礙物環(huán)境如果網(wǎng)格中存在障礙物曼哈頓距離的最短路徑性質(zhì)就被破壞了。因為兩點之間的直線路徑可能被擋住。此時就必須老老實實進(jìn)行BFS或Dijkstra算法如果邊權(quán)不同來模擬。本題沒有障礙物是簡化情況的關(guān)鍵。不同距離度量如果擴散規(guī)則是八方向米字型則使用切比雪夫距離如果是在三維空間曼哈頓距離定義為|dx||dy||dz|。規(guī)則決定距離度量。時間作為距離在這類每分鐘擴散一格的題目中“時間”和“最短路徑長度”是等價的。這啟發(fā)我們在一些問題中可以把時間維度轉(zhuǎn)化為圖論中的路徑長度來思考。理解了這個本質(zhì)后你再看到類似的“擴散”、“感染”、“傳播”問題首先應(yīng)該問自己移動規(guī)則是什么有沒有障礙如果移動規(guī)則簡單如四方向/八方向且沒有障礙那么很可能可以繞過模擬直接用距離公式進(jìn)行高效計算。如果規(guī)則復(fù)雜或有障礙那么BFS/DFS模擬就是唯一可靠的方法。最后關(guān)于這道題的答案我強烈建議你根據(jù)上面的思路自己動手編寫代碼運行并得出結(jié)果。編程競賽的魅力就在于思考和實現(xiàn)的過程。如果你在實現(xiàn)中遇到任何問題比如邊界條件沒處理好導(dǎo)致答案差了幾個或者循環(huán)寫錯了那正是加深理解的好機會。調(diào)試的過程就是對你思維嚴(yán)密性的一次最好訓(xùn)練。