題目描述
給定一個 n * m 的二維整數數組，用來表示一個迷宮，數組中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通過的墻壁。
最初，有一個人位于左上角 (1, 1) 處，已知該人每次可以向上、下、左、右任意一個方向移動一個位置。
請問，該人從左上角移動至右下角 (n, m) 處，至少需要移動多少次。
數據保證 (1, 1) 處和 (n, m) 處的數字為 0，且一定至少存在一條通路。
輸入格式
- 第一行包含兩個整數
n和m。 - 接下來
n行，每行包含m個整數（0或1），表示完整的二維數組迷宮。
輸出格式
輸出一個整數，表示從左上角移動至右下角的最少移動次數。
數據范圍
- 1 ≤ n, m ≤ 100
輸入輸出樣例
樣例輸入 1
復制
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
樣例輸出 1
復制
8
實現思路：
我么使用一個隊列存儲可能的路徑(x,y)，每次拿隊頭的元素判斷下一步可以走的位置，如果可以走且之前沒有走過，那么將該坐標放入隊尾。當隊列不為空就說明有位置可以走，就一直走下去，當所有位置都走完時，右下角的距離就是最短路徑。
這個隊列中的元素是個坐標，所以可以用pair類型存儲，同時隊列的實現可以通過數組+頭尾指針實現：隊頭用hh標記，隊尾用tt標記，開始都初始化為0，拿出隊頭元素t：PII t = q[hh++]（先拿出來隊頭hh再++），當對頭的下一個位置滿足條件時，將其放入隊尾q[++tt]={x,y};（隊尾先++再賦值）
代碼實現
#include<iostream>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
//g用于存儲圖，d用于記錄每個坐標到初始位置的最短距離
int g[N][N], d[N][N];
int n, m;
PII q[N * N]; //q用于存儲每個符合條件的坐標，（即路徑）int bfs()
{//頭尾指針，用于指向模擬隊列int head = 0, tail = 0;q[0] = { 0,0 }; //首先從下標0，0位置開始memset(d, -1, sizeof d); //先將d初始話為-1d[0][0] = 0; //0，0坐標到0，0的距離當然是0啦/** dx和dy用于記錄上下左右四個方向* 如dx[0]dy[0]就表示x-1,y,即向上以一格*/int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 }; while (head <= tail){//先獲取隊列頭頂元素，再head++將其出隊auto t = q[head++];for (int i = 0; i < 4; i++){//表示枚舉該坐標的4個方向int x = t.first + dx[i];int y = t.second + dy[i];//如果這個位置為0（可以走），x<n,y<m(沒出界)，d[x][y]==-1(沒被走過)if (g[x][y] == 0 && x < n && y < m && d[x][y] == -1){//該坐標下的最短路就是上一個坐標的長度+1d[x][y] = d[t.first][t.second] + 1;q[++tail] = { x,y }; //將其入隊}}}return d[n - 1][m - 1];
}
int main()
{cin >> n >> m;for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)cin >> g[i][j];cout << bfs() << endl;return 0;
}
代碼思路總結
通過 廣度優先搜索（BFS） 解決了迷宮最短路徑問題。以下是代碼的詳細思路總結：
1. 問題分析
- 給定一個
n * m的二維數組表示迷宮，0表示通路，1表示墻壁。 - 從起點
(0, 0)出發，每次可以向上、下、左、右移動一個位置，求到達終點(n-1, m-1)的最短路徑長度。
2. 核心思路
- 使用 BFS 逐層遍歷迷宮，確保第一次到達終點時的路徑是最短的。
- 使用一個隊列來存儲待訪問的節點，并通過一個二維數組
d記錄每個節點到起點的最短距離。
3. 代碼實現步驟
(1) 初始化
- 定義二維數組
g存儲迷宮，d存儲每個節點到起點的最短距離。 - 使用
pair<int, int>表示坐標，并用數組q模擬隊列。 - 初始化隊列
q，將起點(0, 0)加入隊列，并設置d[0][0] = 0。
(2) BFS 遍歷
- 使用
while循環不斷從隊列中取出節點，直到隊列為空。 - 對于每個節點，枚舉其四個方向（上、下、左、右）：
- 計算新坐標
(x, y)。 - 檢查新坐標是否合法（未越界、是通路
0、未被訪問過d[x][y] == -1）。 - 如果合法，更新新坐標的最短距離，并將其加入隊列。
- 計算新坐標
(3) 終止條件
- 當遍歷到終點
(n-1, m-1)時，d[n-1][m-1]即為最短路徑長度。
4. 代碼細節解析
(1) 隊列的實現
- 使用數組
q模擬隊列，head和tail分別表示隊頭和隊尾指針。 - 入隊操作：
q[++tail] = {x, y}。 - 出隊操作：
auto t = q[head++]。
(2) 方向數組
-
使用
dx和dy數組表示四個方向的偏移量：cpp
復制
int dx[4] = {-1, 0, 1, 0}; // 上、右、下、左 int dy[4] = {0, 1, 0, -1}; -
通過循環枚舉四個方向，簡化代碼。
(3) 距離數組 d
d[i][j]表示從起點(0, 0)到(i, j)的最短距離。- 初始時，
d數組全部初始化為-1，表示未訪問。 - 每次更新新坐標的距離：
d[x][y] = d[t.first][t.second] + 1。
(4) 邊界檢查
-
檢查新坐標
(x, y)是否在迷宮范圍內：cpp
復制
x < n && y < m -
檢查新坐標是否是通路：
cpp
復制
g[x][y] == 0 -
檢查新坐標是否未被訪問過：
cpp
復制
d[x][y] == -1
5. 復雜度分析
(1) 時間復雜度
- 每個節點最多被訪問一次，因此時間復雜度為 O(n * m)。
(2) 空間復雜度
- 使用了一個隊列和一個距離數組，空間復雜度為 O(n * m)。
6. 示例運行
輸入
復制
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
輸出
復制
8
7. 總結
- 通過 BFS 實現了迷宮最短路徑的求解，利用了隊列的先進先出特性，確保第一次到達終點時的路徑是最短的。
算法刷題日記
)
)
