1. 從“大胖子”到迷宮尋路一個算法題的場景化拆解看到“大胖子走迷宮”這個題目很多參加過藍橋杯或者準備算法競賽的朋友可能會心一笑。這可不是一個簡單的迷宮尋路問題它巧妙地將“角色體積”和“時間”這兩個維度引入了傳統(tǒng)的BFS廣度優(yōu)先搜索框架。我當年第一次遇到這類變種題時也卡了挺久核心難點就在于如何把“胖子會隨時間變瘦”這個動態(tài)規(guī)則無縫整合到每一步的狀態(tài)判斷里。今天我們就來徹底拆解這道來自藍橋杯第十屆國賽Java B組的真題不僅講清楚怎么做更重點剖析為什么這么做以及在實際編碼中那些容易讓人栽跟頭的細節(jié)。這道題的本質(zhì)是一個帶有狀態(tài)擴展的圖搜索問題。迷宮是靜態(tài)的但我們的主角“大胖子”是動態(tài)的他在某些時刻占據(jù)多個格子比如3x3或5x5的范圍并且這個占據(jù)范圍會隨著時間流逝而縮小。這就意味著同一個坐標點(x, y)在不同時間t對于胖子而言的可達性是完全不同的。傳統(tǒng)的BFS記錄(x, y)作為狀態(tài)已經(jīng)不夠用了我們必須將時間t也作為狀態(tài)的一部分形成三維狀態(tài)(x, y, t)。同時胖子的“體型”決定了他在移動時不僅目標點要為空地他身體所覆蓋的所有格子都必須同時為空地。理解并建模好這個“體型覆蓋”邏輯是解題的第一道坎。2. 問題定義與核心狀態(tài)建模我們先拋開代碼用最直白的話把題目規(guī)則翻譯一遍。假設(shè)有一個N x N的網(wǎng)格迷宮用字符矩陣表示‘.’代表空地‘*’代表障礙物。有一個“大胖子”初始位于(sx, sy)他的目標是走到(ex, ey)。胖子的體型隨時間變化規(guī)則通常如下具體參數(shù)需以題目描述為準這里是常見設(shè)定在時間t k時胖子是一個以自身為中心、邊長為5的正方形即占據(jù)5x5的格子區(qū)域。在時間k t 2k時胖子縮小為以自身為中心、邊長為3的正方形即占據(jù)3x3的格子區(qū)域。在時間t 2k時胖子恢復(fù)為正常體型只占據(jù)自身所在的1x1格子。這里k是一個給定的常數(shù)。胖子可以執(zhí)行兩種操作移動向上、下、左、右四個方向移動一格。移動的前提是在移動完成的那個時刻胖子體型所覆蓋的所有格子都必須是空地即‘.’且不能出界。停留在原地等待一個單位時間。胖子可以選擇不行走等待自己變瘦。我們需要求解的是胖子從起點到終點的最短時間。顯然停留操作的存在使得“最短時間”不一定對應(yīng)“最少步數(shù)”因為有時等待變瘦后再走反而比硬闖更省時。2.1 為什么是BFS以及狀態(tài)維度的擴展求最短時間在無權(quán)圖每次移動或停留代價為1中BFS是天然的選擇。但傳統(tǒng)迷宮BFS的狀態(tài)是(x, y)用一個二維數(shù)組vis[x][y]記錄是否訪問過。在這里行不通了因為(x, y)點在不同時間t的可訪問性不同。舉個例子起點旁邊緊挨著一個障礙物。當胖子是5x5體型時他的身體會覆蓋到那個障礙物因此他無法移動或停留在起點如果起點區(qū)域本身有障礙甚至無法開始。他必須等待時間t增加到k體型變?yōu)?x3后如果3x3區(qū)域不包含障礙他才能開始移動。如果3x3區(qū)域還包含障礙則需要等到t 2k變?yōu)?x1。因此我們必須將狀態(tài)定義為(x, y, t)。訪問標記數(shù)組也需要升維vis[x][y][t]這里有個問題時間t可能很大我們無法開一個三維數(shù)組。但仔細分析時間維度存在一個“穩(wěn)態(tài)”當t 2k后胖子的體型不再變化始終為1x1。此后的問題就退化成了標準的迷宮BFS。所以我們只需要關(guān)心從t0到t2k這個動態(tài)變化的過程。對于t 2k的狀態(tài)我們可以用一個統(tǒng)一的“正常體型”狀態(tài)來處理。實際上更常見的做法是不顯式存儲t而是將“體型階段”作為狀態(tài)的一部分。定義狀態(tài)為(x, y, stage)其中stage表示當前的體型階段stage 0: 體型為5x5對應(yīng)t kstage 1: 體型為3x3對應(yīng)k t 2kstage 2: 體型為1x1對應(yīng)t 2k那么時間t如何體現(xiàn)它蘊含在BFS的搜索層數(shù)即步數(shù)/時間中。當我們從隊列中取出一個狀態(tài)(x, y, stage)時我們知道走到這個狀態(tài)所花費的當前時間curTime。根據(jù)curTime我們可以判斷這個狀態(tài)對應(yīng)的stage是否應(yīng)該更新。例如取出狀態(tài)時stage0但curTime k說明胖子已經(jīng)變瘦了我們應(yīng)該將stage更新為1再以此為基礎(chǔ)進行后續(xù)動作的判斷。關(guān)鍵理解stage是胖子在當前時刻的體型屬性而BFS隊列中每個節(jié)點攜帶的時間curTime是用來決定stage是否需要進階的依據(jù)。兩者共同定義了胖子在某一時空下的完整狀態(tài)。2.2 體型覆蓋檢測算法效率的關(guān)鍵無論是移動還是停留都需要判斷“以(x,y)為中心根據(jù)當前stage決定的體型范圍內(nèi)所有格子是否都是空地”。這是一個需要頻繁調(diào)用的操作。假設(shè)迷宮大小N最大為300最壞情況下BFS節(jié)點數(shù)可達N^2 * 3量級約27萬每次判斷如果都樸素地遍歷5x525個格子或3x39個格子計算量約數(shù)百萬次檢查尚可接受但顯然有優(yōu)化空間。優(yōu)化思路二維前綴和我們可以預(yù)處理一個二維前綴和數(shù)組sum[][]其中sum[i][j]表示從(1,1)到(i,j)這個矩形區(qū)域內(nèi)障礙物‘*’的個數(shù)。這樣對于任何以(cx, cy)為中心邊長為len奇數(shù)的正方形區(qū)域其障礙物總數(shù)可以通過前綴和O(1)計算得出障礙數(shù) sum[cxlen/2][cylen/2] - sum[cx-len/2-1][cylen/2] - sum[cxlen/2][cy-len/2-1] sum[cx-len/2-1][cy-len/2-1]如果這個“障礙數(shù)”為0說明該區(qū)域全是空地。在本題中我們只需要判斷“是否全為空地”因此等價于判斷該矩形區(qū)域的“障礙數(shù)”是否為0。預(yù)處理前綴和的時間復(fù)雜度為O(N^2)之后每次體型檢測都是O(1)極大地提升了效率。實操心得在算法競賽中遇到需要頻繁查詢子矩陣和的問題一定要立刻想到二維前綴和。它能把一個O(L^2)的操作降到O(1)是性價比極高的優(yōu)化。編碼時注意處理好邊界可以將迷宮數(shù)據(jù)從1開始存儲方便前綴和計算。3. BFS搜索框架的詳細實現(xiàn)有了以上的分析我們可以搭建BFS的搜索框架了。下面我將分步驟給出實現(xiàn)細節(jié)并解釋每一步的意圖。3.1 數(shù)據(jù)結(jié)構(gòu)與初始化import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int N, K; static char[][] maze; static int[][] sum; // 二維前綴和記錄障礙數(shù) // 方向數(shù)組 static int[] dx {-1, 1, 0, 0}; static int[] dy {0, 0, -1, 1}; // 訪問標記第三維是體型階段 stage (0:5x5, 1:3x3, 2:1x1) static boolean[][][] vis; public static void main(String[] args) { Scanner sc new Scanner(System.in); N sc.nextInt(); K sc.nextInt(); maze new char[N2][N2]; // 從1開始索引方便處理 sum new int[N2][N2]; vis new boolean[N2][N2][3]; for (int i 1; i N; i) { String line sc.next(); for (int j 1; j N; j) { maze[i][j] line.charAt(j-1); // 計算前綴和如果是障礙物則值為1 int val (maze[i][j] *) ? 1 : 0; sum[i][j] sum[i-1][j] sum[i][j-1] - sum[i-1][j-1] val; } } // 假設(shè)起點為(1,1)終點為(N, N)具體以題目輸入為準 int ans bfs(1, 1, N, N); System.out.println(ans); } }說明數(shù)組開N2是為了方便處理邊界避免在判斷前綴和時頻繁檢查下標是否小于1。vis[x][y][stage]記錄狀態(tài)(x, y, stage)是否已被訪問。注意同一個坐標(x,y)在不同stage下被視為不同狀態(tài)。前綴和sum[i][j]的計算采用了動態(tài)規(guī)劃的思想是這類問題的標準寫法。3.2 核心函數(shù)檢查當前位置是否合法這是整個算法的基石需要根據(jù)當前的stage體型來判斷胖子能否位于(x, y)點。// 判斷在階段stage下中心點在(cx, cy)的位置是否合法即體型覆蓋區(qū)域全為空地 static boolean check(int cx, int cy, int stage) { int len; // 體型的邊長 if (stage 0) len 5; else if (stage 1) len 3; else len 1; // stage 2 // 計算體型區(qū)域的左上角和右下角坐標 int half len / 2; // 對于5-2, 3-1, 1-0 int x1 cx - half; int y1 cy - half; int x2 cx half; int y2 cy half; // 首先檢查邊界體型區(qū)域不能超出迷宮范圍[1, N] if (x1 1 || y1 1 || x2 N || y2 N) { return false; } // 利用前綴和檢查該矩形區(qū)域內(nèi)是否有障礙物 int obstacleCnt sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] sum[x1-1][y1-1]; return obstacleCnt 0; }避坑提示邊界檢查必須放在前綴和查詢之前。因為如果體型區(qū)域越界我們?nèi)ゲ樵僺um[x2][y2]時下標可能非法導(dǎo)致數(shù)組越界錯誤。這是一個非常常見的編碼失誤點。3.3 BFS搜索過程詳解BFS隊列中的節(jié)點需要存儲x坐標、y坐標、到達該狀態(tài)的時間以及到達時的體型階段。由于stage可以從curTime推導(dǎo)也可以顯式存儲。顯式存儲邏輯更清晰。static class Node { int x, y, time, stage; Node(int x, int y, int time, int stage) { this.x x; this.y y; this.time time; this.stage stage; } } static int bfs(int sx, int sy, int ex, int ey) { QueueNode queue new LinkedList(); // 初始狀態(tài)檢查如果起點在初始體型下就不合法則無法開始 if (!check(sx, sy, 0)) { // 可能需要等待不題目通常保證起點初始合法或允許等待。這里先嘗試加入。 // 更嚴謹?shù)淖龇ㄊ菍⑵瘘c狀態(tài)加入時其stage應(yīng)根據(jù)當前時間0計算。 } // 初始節(jié)點時間0階段0。但加入隊列前其stage應(yīng)根據(jù)時間0確定。 int initStage getStage(0); if (!check(sx, sy, initStage)) { // 如果起點在初始階段就不合法說明需要等待。但BFS起點就是等待的開始。 // 我們可以選擇將(時間0, 階段0)加入在彈出時處理階段更新。 // 另一種思路直接將(sx, sy, 0, 0)加入但在處理節(jié)點時先根據(jù)其time更新stage。 } vis[sx][sy][initStage] true; queue.offer(new Node(sx, sy, 0, initStage)); while (!queue.isEmpty()) { Node cur queue.poll(); int cx cur.x, cy cur.y, ct cur.time, cs cur.stage; // 彈出節(jié)點后首先根據(jù)當前時間ct更新其真實的體型階段rs (real stage) int rs getStage(ct); // 注意如果cs與rs不同意味著我們在隊列中存儲的stage是過時的。 // 我們需要以更新后的rs為準進行后續(xù)操作。 // 因此檢查當前狀態(tài)是否合法應(yīng)用rs。 if (!check(cx, cy, rs)) { continue; // 當前狀態(tài)不合法跳過例如在隊列中等待時體型縮小后發(fā)現(xiàn)當前位置被障礙卡住 } // 到達終點判斷必須在體型為1x1時即rs2站在終點才算成功 if (cx ex cy ey rs 2) { return ct; } // 擴展動作停留和四個方向的移動 // 動作1停留 int nt ct 1; int ns getStage(nt); // 下一時刻的體型階段 if (!vis[cx][cy][ns]) { vis[cx][cy][ns] true; queue.offer(new Node(cx, cy, nt, ns)); } // 動作2向四個方向移動 for (int i 0; i 4; i) { int nx cx dx[i]; int ny cy dy[i]; // 移動后的階段使用下一時刻的階段ns if (nx 1 nx N ny 1 ny N !vis[nx][ny][ns]) { // 關(guān)鍵判斷移動是否合法要看在下一時刻ns階段下新位置(nx, ny)是否合法 if (check(nx, ny, ns)) { vis[nx][ny][ns] true; queue.offer(new Node(nx, ny, nt, ns)); } } } } return -1; // 無法到達 } // 根據(jù)時間t返回對應(yīng)的體型階段 static int getStage(int t) { if (t K) return 0; else if (t 2 * K) return 1; else return 2; }逐段解析節(jié)點定義與初始化Node類包含了位置、時間和階段。初始化時根據(jù)時間0計算出初始階段initStage并標記訪問。這里隱含了“起點在初始時刻必須是合法的”這一常見題目條件。狀態(tài)更新從隊列中取出節(jié)點cur后第一件事就是用cur.time重新計算真實的階段rs。為什么因為節(jié)點入隊時存儲的stage是基于入隊時的time計算的。在隊列中等待被處理的過程中time沒有變但當我們處理它時是以它被取出時的視角來看的。實際上由于BFS按時間遞增順序擴展cur.time就是該狀態(tài)發(fā)生的時刻用這個時刻計算rs是準確的。cscur.stage在入隊后就沒有意義了我們以rs為準。合法性復(fù)查用rs檢查當前位置是否合法。這一步很重要考慮一種情況胖子以5x5體型移動到一個位置然后這個位置在3x3體型下是合法的但他在隊列中“等待”時時間流逝體型變?yōu)?x3此時需要復(fù)查該位置是否依然合法。如果因為體型縮小原來被身體邊緣覆蓋的障礙物現(xiàn)在“進入”了身體內(nèi)部導(dǎo)致位置非法那么這個狀態(tài)就應(yīng)該被丟棄。終點判斷題目通常要求胖子以正常體型1x1到達終點。所以判斷條件不僅是坐標匹配還要rs 2。動作擴展停留時間1階段變?yōu)間etStage(ct1)。如果該新狀態(tài)未訪問則入隊。這里有一個關(guān)鍵點停留后位置不變但時間增加了階段可能變化。移動計算下一個位置(nx, ny)時間同樣是ct1階段為ns。移動的合法性判斷是在下一時刻nt處于下一階段ns的胖子其身體覆蓋區(qū)域在新位置(nx, ny)上必須全部是空地。這個判斷調(diào)用的是check(nx, ny, ns)而不是check(nx, ny, rs)。3.4 為什么不需要在移動判斷中檢查當前狀態(tài)細心的讀者可能會問移動時不需要保證從當前位置移動一格這個動作本身是合法的嗎比如胖子當前是5x5他向右移動一格在移動過程中他5x5的身體是否會蹭到右邊的障礙物在我們的模型里這個檢查已經(jīng)蘊含在check(nx, ny, ns)之中了。我們假設(shè)移動是瞬時的在t時刻末胖子還在(cx, cy)在t1時刻初胖子已經(jīng)到達(nx, ny)。我們只關(guān)心在t1時刻胖子在(nx, ny)處是否合法。這符合題目的離散時間模型。不需要考慮移動過程中的“碰撞檢測”。4. 常見錯誤與性能優(yōu)化陷阱即使理解了算法實現(xiàn)時依然會遇到不少坑。下面我結(jié)合自己的調(diào)試經(jīng)驗列舉幾個高頻錯誤點。4.1 狀態(tài)重復(fù)訪問與剪枝BFS必須要有訪問標記來避免重復(fù)訪問否則隊列會無限膨脹。這里的狀態(tài)是(x, y, stage)。為什么是stage而不是time因為對于同一個(x, y)如果stage相同那么無論time是多少胖子在此處的“行動能力”是相同的因為體型相同。后續(xù)從該狀態(tài)出發(fā)能擴展出的路徑其時間差是固定的。如果允許相同(x, y, stage)的狀態(tài)被多次訪問后訪問的狀態(tài)其time一定大于等于先訪問的狀態(tài)因此不可能產(chǎn)生更優(yōu)解時間更短。所以用vis[x][y][stage]剪枝是正確的。一個易錯場景胖子在(x,y)點stage05x5時間t1時被訪問。之后他在別處等待時間tK此時stage應(yīng)變?yōu)?時又想到達(x,y)點。此時他訪問的是(x,y, stage1)這是一個新狀態(tài)即使坐標相同也是允許的。我們的vis數(shù)組第三維正好區(qū)分了這一點。4.2 時間與階段更新的同步問題這是最核心的易錯點?？匆韵掠袉栴}的偽代碼// 錯誤示例 Node cur queue.poll(); if (cur.stage 0 cur.time K) { cur.stage 1; } // ... 然后用cur.stage去進行check和擴展錯誤在于修改了cur對象的屬性并且用更新后的stage去判斷移動合法性。但移動發(fā)生在下一時刻cur.time1其階段應(yīng)該是getStage(cur.time1)而不是更新后的cur.stage。正確的做法如前文所述引入一個局部變量realStage getStage(cur.time)用于當前狀態(tài)判斷而擴展動作時使用nextStage getStage(cur.time1)。4.3 起點/終點合法性處理的邊界情況題目可能不會明確保證起點在初始時刻t0,stage0是合法的。例如起點本身是空地但胖子初始5x5的身體覆蓋了周圍的障礙物。根據(jù)規(guī)則此時胖子無法“存在”于起點。那該怎么辦題目通常隱含允許“等待”。也就是說胖子的起始狀態(tài)是“在起點等待直到體型縮小到可以容納為止”。我們的BFS初始化需要處理這種情況。一種方法是不直接將(sx, sy, 0, 0)設(shè)為初始狀態(tài)而是將“在起點等待”這個動作也納入BFS。我們可以虛擬一個開始或者更簡單地檢查getStage(0)下的起點是否合法。如果不合法則根本不能將起點狀態(tài)加入隊列。但題目要求求最短時間如果起點初始不合法最短時間可能就是他從“不存在”到“存在”的等待時間。更通用的初始化方法是// 尋找第一個可以使起點合法的時刻作為BFS起點 int startTime 0; while (startTime 2*K !check(sx, sy, getStage(startTime))) { startTime; } if (startTime 2*K) { // 即使變?yōu)?x1也不合法說明起點有障礙直接輸出-1或根據(jù)題意處理 } int startStage getStage(startTime); vis[sx][sy][startStage] true; queue.offer(new Node(sx, sy, startTime, startStage));這樣BFS的起點時間就不是0而是胖子在起點能夠“站穩(wěn)”的第一個時刻。這個邏輯更完備。4.4 二維前綴和的邊界處理這是實現(xiàn)細節(jié)上的坑。我們的迷宮下標從1開始sum[0][j]和sum[i][0]都應(yīng)初始化為0。在check函數(shù)中計算矩形和時x1-1或y1-1可能為0這正是前綴和公式能正確工作的前提sum[0][*] sum[*][0] 0。如果數(shù)組從0開始存儲就需要在計算時增加更多的條件判斷容易出錯。因此強烈建議將迷宮數(shù)據(jù)存儲在1-indexed的數(shù)組中。5. 完整代碼參考與測試思路將上述所有部分整合并加入一些健壯性判斷得到完整代碼。這里假設(shè)輸入格式為第一行兩個整數(shù) N 和 K接下來 N 行每行 N 個字符表示迷宮起點(1,1)終點(N,N)。import java.util.*; public class FatManMaze { static int N, K; static char[][] g; static int[][] sum; static boolean[][][] vis; static int[] dirx {-1, 1, 0, 0}; static int[] diry {0, 0, -1, 1}; static class Node { int x, y, time, stage; public Node(int x, int y, int time, int stage) { this.x x; this.y y; this.time time; this.stage stage; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); N sc.nextInt(); K sc.nextInt(); g new char[N2][N2]; sum new int[N2][N2]; vis new boolean[N2][N2][3]; for (int i 1; i N; i) { String s sc.next(); for (int j 1; j N; j) { g[i][j] s.charAt(j-1); int val g[i][j] * ? 1 : 0; sum[i][j] sum[i-1][j] sum[i][j-1] - sum[i-1][j-1] val; } } int ans bfs(); System.out.println(ans); sc.close(); } static int bfs() { QueueNode q new LinkedList(); int startX 1, startY 1, endX N, endY N; // 初始化找到起點第一個合法時刻 int startTime 0; while (startTime 2 * K !check(startX, startY, getStage(startTime))) { startTime; } if (startTime 2 * K) { // 即使變成1x1起點也不合法起點是障礙 return -1; } int startStage getStage(startTime); vis[startX][startY][startStage] true; q.offer(new Node(startX, startY, startTime, startStage)); while (!q.isEmpty()) { Node cur q.poll(); int cx cur.x, cy cur.y, ct cur.time, cs cur.stage; // 根據(jù)當前時間確定真實階段 int rs getStage(ct); // 復(fù)查當前狀態(tài)合法性針對等待后體型變化的情況 if (!check(cx, cy, rs)) { continue; } // 終點判斷 if (cx endX cy endY rs 2) { return ct; } int nt ct 1; int ns getStage(nt); // 動作1: 停留 if (!vis[cx][cy][ns]) { vis[cx][cy][ns] true; q.offer(new Node(cx, cy, nt, ns)); } // 動作2: 移動 for (int d 0; d 4; d) { int nx cx dirx[d]; int ny cy diry[d]; if (nx 1 || nx N || ny 1 || ny N) continue; if (vis[nx][ny][ns]) continue; if (check(nx, ny, ns)) { vis[nx][ny][ns] true; q.offer(new Node(nx, ny, nt, ns)); } } } return -1; // 無法到達 } static boolean check(int cx, int cy, int stage) { int len; if (stage 0) len 5; else if (stage 1) len 3; else len 1; int half len / 2; int x1 cx - half; int y1 cy - half; int x2 cx half; int y2 cy half; // 邊界檢查 if (x1 1 || y1 1 || x2 N || y2 N) { return false; } // 前綴和查詢區(qū)域是否有障礙 int obs sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] sum[x1-1][y1-1]; return obs 0; } static int getStage(int t) { if (t K) return 0; else if (t 2 * K) return 1; else return 2; } }測試建議簡單通路小迷宮無障礙直接測試BFS基本功能。需要等待設(shè)置一個狹窄通道寬度為1但長度方向無障礙。起點在通道一端。初始5x5體型無法進入通道必須等待至3x3或1x1才能進入。驗證程序是否選擇了等待。起點被卡起點是空地但周圍緊挨著障礙物使得5x5體型不合法。驗證程序是否能通過等待找到起始時間?；旌下窂皆O(shè)計一個迷宮其中一條路徑短但需要長時間等待如穿過一個最初很窄的走廊另一條路徑長但無需等待。驗證程序是否能正確選擇總時間更短的路徑可能是等待短路徑。大尺寸壓力測試N300隨機生成障礙物測試程序在極限數(shù)據(jù)下的運行時間和內(nèi)存是否可接受Java下應(yīng)能在1-2秒內(nèi)完成。這道“大胖子走迷宮”題目融合了BFS、狀態(tài)壓縮、前綴和優(yōu)化以及對題目規(guī)則的細致建模是檢驗選手綜合思維和代碼實現(xiàn)能力的一道好題。理解其核心——將時間維度轉(zhuǎn)化為體型階段并將此階段作為狀態(tài)的一部分進行搜索——是解決所有類似動態(tài)障礙或動態(tài)角色問題的鑰匙。在編碼時時刻分清“當前狀態(tài)”和“動作后的狀態(tài)”處理好階段與時間的同步關(guān)系就能穩(wěn)穩(wěn)拿下這類題目。