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