一、引言：探索迷宮的智能方法

在解決迷宮最短路徑問題時，廣度優先搜索（BFS）是一種高效而優雅的算法。與深度優先搜索（DFS）不同，BFS采用"由近及遠"的搜索策略，逐層探索所有可能的路徑，從而保證首次到達終點時的路徑就是最短路徑。（對深搜沒有了解的同學，可以先看下我寫的關于深搜的學習文章）

二、問題描述：迷宮尋路

給定一個R行C列的迷宮，迷宮由'.'（空地）和'#'（障礙物）組成。我們需要計算從左上角（入口）到右下角（出口）的最短步數（包括起點和終點）。移動規則：每次只能向上、下、左、右四個方向移動到相鄰的空地格子。

輸入示例：

5 5
..###
#....
#.#.#
#.#.#
#.#..

輸出示例：

9

三、BFS算法核心思想

BFS采用隊列（Queue）?這一數據結構實現"先進先出"的訪問策略：

1. 從起點開始，將其加入隊列

2. 取出隊首元素，探索其所有相鄰位置

3. 將未訪問的有效位置加入隊列

4. 重復直到找到終點或隊列為空

這種策略確保算法優先訪問距離起點更近的位置，因此首次到達終點時的路徑必然是最短路徑。

四、完整代碼實現

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;int R, C; // 迷宮的行數和列數
char maze[40][40]; // 存儲迷宮
bool visited[40][40]; // 標記訪問狀態// 方向數組：右(0,1), 下(1,0), 上(0,-1), 左(-1,0)
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};// 位置結構體：存儲坐標和步數
struct Position {int x, y; // 當前坐標int steps; // 從起點到當前位置的步數
};int bfs() {queue<Position> q;// 起點入隊：位置(0,0)，步數為1（包括起點）q.push({0, 0, 1});visited[0][0] = true; // 標記起點已訪問while (!q.empty()) {Position current = q.front();q.pop();// 到達終點：右下角(R-1, C-1)if (current.x == R - 1 && current.y == C - 1) {return current.steps;}// 探索四個方向for (int i = 0; i < 4; i++) {int nx = current.x + dx[i]; // 新位置的行坐標int ny = current.y + dy[i]; // 新位置的列坐標// 檢查新位置是否有效if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue; // 超出邊界if (maze[nx][ny] == '#') continue; // 遇到障礙物if (visited[nx][ny]) continue; // 已訪問過// 有效位置：標記并加入隊列visited[nx][ny] = true;q.push({nx, ny, current.steps + 1});}}// 如果沒有找到路徑（題目保證有解，此返回值不會執行）return -1;
}int main() {// 讀入迷宮大小cin >> R >> C;// 讀入迷宮數據for (int i = 0; i < R; i++) {for (int j = 0; j < C; j++) {cin >> maze[i][j];}}// 初始化訪問標記數組memset(visited, false, sizeof(visited));// 執行BFS并輸出結果cout << bfs() << endl;return 0;
}

五、關鍵代碼解析

1. 方向數組：簡潔的方向控制

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

這兩個數組定義了四個基本移動方向：

• 右：(x+0, y+1)

• 下：(x+1, y+0)

• 左：(x+0, y-1)

• 上：(x-1, y+0)

使用方向數組避免了重復的方向判斷代碼，使程序更簡潔。

2. 位置結構體：信息封裝

struct Position {int x, y; // 當前位置坐標int steps; // 從起點到當前位置的步數
};

結構體封裝了位置信息和步數，便于在隊列中存儲和傳遞狀態。

3. BFS核心邏輯：逐層探索

while (!q.empty()) {Position current = q.front();q.pop();// 檢查是否到達終點// 探索四個方向for (int i = 0; i < 4; i++) {// 計算新位置// 檢查新位置有效性（邊界、障礙、訪問狀態）// 有效位置入隊}
}

這是BFS的核心循環，每次從隊列中取出最早加入的位置（距離起點最近），探索其所有相鄰位置。

4. 訪問標記：避免重復訪問

visited[nx][ny] = true;

每個位置在首次訪問時被標記，確保每個位置只被訪問一次，避免無限循環和不必要的重復計算。

六、BFS與DFS的對比

特性	BFS	DFS
數據結構	隊列（Queue）	棧（Stack）
搜索策略	廣度優先，逐層擴展	深度優先，沿路徑到底
空間復雜度	O(最寬層的節點數)	O(最大深度)
最短路徑	首次到達即是最短路徑	需要遍歷所有路徑找最短
適用場景	無權圖最短路徑問題	所有路徑遍歷，連通性檢查

在迷宮最短路徑問題中，BFS具有明顯優勢，因為它無需遍歷所有路徑就能找到最短路徑。

七、總結

廣度優先搜索是解決迷宮最短路徑問題的經典算法，其核心在于：

• 使用隊列管理待訪問位置

• 逐層探索保證首次到達終點即是最短路徑

• 通過訪問標記避免重復計算