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