1. 從“擴散”到“廣度優先”一道國賽題的思維躍遷看到“擴散”這個詞很多人的第一反應可能是物理現象或者圖像處理。但在2020年藍橋杯國賽C B組的賽場上它被賦予了一個全新的、充滿算法趣味的定義。這道題沒有冗長的背景故事題干本身可能只有寥寥數語但它精準地考察了選手將實際問題抽象為圖論模型并運用廣度優先搜索BFS這一基礎算法高效求解的能力。這恰恰是算法競賽的魅力所在——用簡潔的規則構建復雜的邏輯世界。這道題的核心可以這樣理解在一個無限的二維網格平面上最初有四個點被“感染”或稱為“黑點”。每一分鐘每個被感染的點會向其上、下、左、右四個相鄰的網格點擴散感染。問題通常會是在第2020分鐘或者某個特定的時間T結束時有多少個網格點被感染了初看之下這似乎是一個模擬題直接開一個足夠大的數組每分鐘更新狀態不就行了但“無限平面”和“2020分鐘”這兩個條件結合在一起立刻排除了暴力模擬的可行性。2020分鐘的擴散最遠影響距離可能達到2020*48080個網格單位如果四個點朝一個方向擴散這意味著模擬區域邊長可能超過16000數組大小將是一個天文數字無論是時間還是空間復雜度都無法承受。因此這道題的關鍵在于發現規律、建立模型、優化求解。它要求選手跳出“模擬每一步”的慣性思維轉而思考感染傳播的本質——距離。2. 問題本質剖析曼哈頓距離與感染區域要高效解決這個問題我們首先要進行數學抽象。將初始的四個感染點視為平面上的四個源點。根據規則感染每分鐘向四鄰域擴散一步。那么一個網格點(x, y)在t時刻被感染的條件是什么它意味著存在一個初始源點(x0, y0)從該源點走到(x, y)所需的步數即時間小于等于t。并且由于每分鐘只能走一步上、下、左、右這個步數就是兩點之間的曼哈頓距離Manhattan Distance。曼哈頓距離公式為d |x - x0| |y - y0|。所以(x, y)在t時刻被感染的條件是存在一個初始源點使得該點到(x, y)的曼哈頓距離d t。這樣一來問題發生了根本性的轉變我們不需要模擬時間流逝只需要計算在曼哈頓距離t范圍內能被至少一個源點覆蓋的所有整數坐標點(x, y)的個數。這變成了一個計算幾何問題更具體地說是計算多個菱形曼哈頓距離下的“圓”的并集所包含的整數點個數。每個源點(x0, y0)在曼哈頓距離t下的覆蓋區域是一個中心在(x0, y0)、對角線豎直水平的菱形或者說是一個旋轉了45度的正方形。2.1 從無限平面到有限區域確定搜索邊界雖然平面是無限的但我們需要計算的只是距離四個源點t步以內的點。因此我們可以輕松確定一個有限的矩形區域作為搜索范圍。設四個初始點的坐標分別為(xi, yi)其中i1,2,3,4。 計算所有點的最小橫坐標min_x最大橫坐標max_x最小縱坐標min_y最大縱坐標max_y。 那么在t時刻所有可能被感染的點一定落在以下矩形區域內x 的范圍[min_x - t, max_x t] y 的范圍[min_y - t, max_y t]這個區域的大小是有限的邊長大約在(max_x - min_x 2*t 1)和(max_y - min_y 2*t 1)這個量級。對于t2020和初始點坐標范圍不大的情況這個區域是完全可以遍歷的。2.2 暴力枚舉法的可行性分析基于以上分析最直接的算法浮出水面雙重循環遍歷上述矩形區域內的每一個整數點(x, y)對于每個點計算其到四個源點的曼哈頓距離如果有一個距離 t則該點被感染計數器加一。我們來估算一下計算量。假設初始點坐標絕對值在100以內t2020那么矩形區域邊長大約為1002020*2 ≈ 4140?？傸c數約為4140 * 4140 ≈ 17, 139, 600即1700萬量級。對于每個點需要計算4次曼哈頓距離4次絕對值加法比較?？偛僮鞔螖导s為1700萬 * 4 6800萬次基本運算。在現代計算機上C完成6800萬次簡單運算是完全可行的通常在1秒以內。因此暴力枚舉法對于本題的規模是切實可行的。這也是本題被歸為B組題目的原因之一它鼓勵選手先找到正確的數學模型然后采用直觀且有效的方法實現。注意這里體現了算法競賽中的一個重要思維——復雜度估算。在動手前先對問題規模和處理器的能力做一個粗略估計能避免走入死胡同也能為優化提供方向。3. 算法實現細節與BFS的對照雖然暴力枚舉足夠解題但題目名稱中的“擴散”很容易讓人聯想到BFS。我們不妨也探討一下BFS的思路并對比其優劣這能加深對問題本質的理解。3.1 廣度優先搜索BFS思路BFS模擬了感染擴散的實時過程將四個初始點加入隊列并標記為已訪問。每次從隊列中取出一個點(x, y)將其步數時間記為step。如果step t則遍歷其四個鄰居(nx, ny)。如果鄰居未被訪問過則將其步數設為step1標記為已訪問并加入隊列。重復步驟2-4直到隊列為空。統計所有被標記訪問過的點的數量即為答案。BFS的潛在問題空間開銷大我們需要記錄每個點是否被訪問過。由于點可能分布在一個很大的矩形區域我們需要使用一個高效的判重數據結構。使用STL的std::set或std::unordered_set來存儲點的坐標例如pairint, int在插入和查詢時會有較大的時間開銷對數或平均常數時間但常數較大。當感染點數量達到百萬級時這個開銷可能變得顯著。時間開銷BFS需要顯式地探索每一個被感染的點及其鄰居。最終被感染的點數量就是我們需要統計的答案假設為N。那么BFS的過程本身就需要進行大約N * 4次的鄰居檢查和隊列操作。對于t2020的情況N本身可能就在千萬量級這導致BFS的總操作次數與暴力枚舉法處于同一量級甚至更多且每次操作集合查找、插入的成本更高。3.2 暴力枚舉法的實現要點相比之下暴力枚舉法實現更簡單且通常更快。以下是C實現的核心步驟定義初始點與時間T// 假設初始點坐標根據題目具體給出這里是示例 int points[4][2] {{0, 0}, {2020, 11}, {11, 14}, {2000, 2000}}; int T 2020;確定搜索邊界int min_x points[0][0], max_x points[0][0]; int min_y points[0][1], max_y points[0][1]; for (int i 1; i 4; i) { min_x min(min_x, points[i][0]); max_x max(max_x, points[i][0]); min_y min(min_y, points[i][1]); max_y max(max_y, points[i][1]); } int start_x min_x - T; int end_x max_x T; int start_y min_y - T; int end_y max_y T;雙重循環遍歷與判斷long long ans 0; // 使用long long防止溢出 for (int x start_x; x end_x; x) { for (int y start_y; y end_y; y) { bool infected false; for (int i 0; i 4; i) { int dx abs(x - points[i][0]); int dy abs(y - points[i][1]); if (dx dy T) { infected true; break; // 找到一個可達源點即可 } } if (infected) { ans; } } } cout ans endl;為什么暴力枚舉在此處更優內存訪問連續雙重循環遍歷一個虛擬的矩形區域內存訪問模式是連續且可預測的對CPU緩存友好。計算極其簡單核心計算是整數加減、絕對值和比較現代CPU可以在一個時鐘周期內完成多條這樣的指令。無額外數據結構開銷不需要維護隊列、集合等動態數據結構避免了內存分配和復雜查找的開銷。實操心得在算法競賽中最簡單的辦法往往就是最好的辦法前提是你能通過復雜度分析確認它不會超時。不要因為題目叫“擴散”就非得用BFS。先建模再選算法。4. 優化進階從O(N2)到O(N)的思維暴力枚舉法的時間復雜度是O(W * H * 4)其中W和H是搜索區域的寬度和高度。這本質上與感染面積點數N乘以一個常數成正比可以認為是O(N)的因為需要遍歷可能區域內的每個點進行檢查。但有沒有可能不遍歷這么多點直接計算出答案呢答案是肯定的這需要更深入的數學工具。我們可以把問題轉化為求四個菱形的并集面積整數點個數。求多個凸多邊形的并集面積有標準的算法如掃描線算法。4.1 掃描線算法思路簡介對于每個源點產生的菱形我們可以求出它在每一行y坐標固定上覆蓋的x坐標范圍。因為菱形是中心對稱的對于源點(x0, y0)和距離t在縱坐標y這一行能被覆蓋的橫坐標x需要滿足|x - x0| |y - y0| t即|x - x0| t - |y - y0|令remain t - |y - y0|如果remain 0則這一行沒有任何點被該源點覆蓋。 否則覆蓋的x區間為[x0 - remain, x0 remain]。這樣對于每一個y我們都能得到來自四個源點的最多四個區間。問題就變成了對于固定的y求這四個區間的并集長度然后將所有y對應的并集長度累加。求多個區間的并集長度是一個經典問題可以通過區間合并算法在O(m log m)內解決m是區間數這里最大為4。4.2 掃描線算法實現框架確定y的掃描范圍[min_y - t, max_y t]。對范圍內的每一個整數y a. 初始化一個空的區間向量intervals。 b. 對于每個源點(x0, y0)計算remain t - abs(y - y0)。 c. 如果remain 0則將區間[x0 - remain, x0 remain]加入intervals。 d. 對intervals按左端點排序然后進行區間合并計算出這些區間在x軸上的總覆蓋長度len。 e. 將len累加到答案ans中。輸出ans。復雜度分析y的掃描范圍大小約為O(t)對于每個y進行4次計算和一次最多4個區間的合并O(1)。總復雜度為O(t)這比暴力枚舉的O(t2)有顯著提升。當t很大時比如t10^9這種方法的優勢是決定性的。代碼片段示例區間合并部分// intervals 是一個 vectorpairint, int 存儲了 [l, r] 區間 sort(intervals.begin(), intervals.end()); long long total_len 0; int cur_l intervals[0].first, cur_r intervals[0].second; for (int i 1; i intervals.size(); i) { if (intervals[i].first cur_r 1) { // 注意曼哈頓距離覆蓋的是整數點區間[1,2]和[3,4]是連續的因為點2和點3相鄰。 cur_r max(cur_r, intervals[i].second); } else { total_len (cur_r - cur_l 1); cur_l intervals[i].first; cur_r intervals[i].second; } } total_len (cur_r - cur_l 1); ans total_len;關鍵細節在區間合并判斷是否連續時條件應該是intervals[i].first cur_r 1而不是intervals[i].first cur_r。因為cur_r是上一個區間覆蓋的最后一個整數點下一個區間如果從cur_r1開始這兩個區間在整數點上是連續的。這是本題用掃描線算法時最容易出錯的地方。5. 調試、驗證與常見“坑點”無論采用哪種方法正確的實現都需要經過驗證。以下是幾個關鍵的驗證點和常見錯誤5.1 邊界與數據類型坐標范圍初始點坐標和t可能為負數嗎題目通常會給明確坐標。我們的搜索邊界計算min_x - t要考慮到負數情況。整數溢出這是最大的“坑”。t2020時答案可能很大。假設每個源點獨立擴散一個點覆蓋的面積大約是2*t^2量級菱形面積近似。四個點即使有重疊答案也可能達到千萬甚至上億。因此用于計數的變量如ans必須使用long long64位整數。在C中int通常是32位最大值約21億在本題數據規模下有可能溢出。循環邊界在暴力枚舉中for循環的邊界是 end_x而不是 end_x務必確認。5.2 驗證策略小數據測試用小的t如1, 2, 3手動計算或編寫一個簡單的BFS程序進行驗證。比較暴力枚舉、掃描線、BFS三種方法的結果是否一致。對稱性檢驗如果初始點關于某條直線對稱那么感染區域也應該對稱。可以利用這個性質檢查程序輸出是否合理。時間增長驗證觀察t每增加1答案的增加量是否符合預期。感染區域的增長應該是有規律的。5.3 針對本題的特定陷阱初始點重合題目并未說明四個初始點是否互異。如果存在重合點在計算時它們應被視為同一個源點。但在我們的算法中無論是暴力枚舉距離判斷還是掃描線區間生成重合點都不會導致重復計數因為判斷條件是“存在一個源點滿足距離t”多個重合源點與一個源點的效果相同。不過在確定搜索邊界時如果直接用重合點計算min_x, max_x等結果依然是正確的。時間起點明確“第2020分鐘結束時”的含義。通常t0表示初始狀態已有4個點被感染。那么t1時感染點會增加。我們的算法中“距離 t” 對應的是t時刻結束時包括初始時刻的狀態。這一點需要與題目描述嚴格對照。6. 從解題到舉一反三模型拓展與應用解完一道題價值在于其背后的模型和思想能否遷移。這道“擴散”題至少給了我們三點啟示曼哈頓距離與網格BFS的等價性在四鄰域網格中兩點最短路徑步數等于其曼哈頓距離。因此所有基于等速四向擴散/傳播的問題都可以轉化為曼哈頓距離的覆蓋問題。這比BFS更本質也常常更高效。離散幾何中的計數問題計算多個規則圖形如菱形、正方形并集內的整數點個數是一類經典問題。掃描線區間合并是解決一維投影疊加的利器。如果擴散是八方向切比雪夫距離那么覆蓋區域就變成了正方形問題會變得更簡單。復雜度分析的直覺訓練面對“無限平面”、“長時間擴散”第一反應不應該是開大數組而應該是分析增長規律。通過計算曼哈頓距離我們將一個時間O(t)、空間O(t2)的模擬問題轉化為了一個時間O(t2)甚至O(t)、空間O(1)的計數問題。這種思維轉換是解決競賽難題的關鍵。在實際編程中我個人的習慣是先嘗試最直觀的暴力方法并立刻進行最壞情況下的復雜度估算。如果估算結果在可接受范圍內例如本題的千萬次運算就優先實現它因為它通常代碼簡單不易出錯。如果暴力法不可行再深入分析問題結構尋找像曼哈頓距離、掃描線這樣的優化突破口。這道2020年國賽題就是一個絕佳的范例展示了如何將一道看似需要模擬的題通過數學洞察變成一個簡潔優美的計數問題。