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