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