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