# 二進制迷宮中的最短路徑 > 原文： [https://www.geeksforgeeks.org/shortest-path-in-a-binary-maze/](https://www.geeksforgeeks.org/shortest-path-in-a-binary-maze/) 給定一個 MxN 矩陣，其中每個元素可以為 0 或 1。我們需要找到給定源單元格到目標單元格之間的最短路徑。 如果路徑的值為 1，則只能在單元格外部創建路徑。 預期時間復雜度為 O（MN）。 例如 - ``` Input: mat[ROW][COL] = {{1, 0, 1, 1, 1, 1, 0, 1, 1, 1 }, {1, 0, 1, 0, 1, 1, 1, 0, 1, 1 }, {1, 1, 1, 0, 1, 1, 0, 1, 0, 1 }, {0, 0, 0, 0, 1, 0, 0, 0, 0, 1 }, {1, 1, 1, 0, 1, 1, 1, 0, 1, 0 }, {1, 0, 1, 1, 1, 1, 0, 1, 0, 0 }, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, {1, 0, 1, 1, 1, 1, 0, 1, 1, 1 }, {1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }}; Source = {0, 0}; Destination = {3, 4}; Output: Shortest Path is 11 ``` 這個想法的靈感來自 [Lee 算法](https://en.wikipedia.org/wiki/Lee_algorithm)，并使用了 BFS。 1. 我們從源單元開始，并調用 BFS 過程。 2. 我們維護一個隊列來存儲矩陣的坐標，并使用源單元格對其進行初始化。 3. 我們還維護一個布爾數組，該數組的大小與輸入矩陣的大小相同，并將其所有元素初始化為 false。 1. 我們循環直到隊列不為空 2. 從隊列中取出前端單元 3. 如果到達目標坐標，則返回。 4. 對于其四個相鄰單元格中的每個單元格，如果值為 1 并且尚未訪問它們，我們將其排隊在隊列中，并將它們標記為已訪問。 **請注意**， [BFS](http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/) 在這里可以正常使用，因為它不會一次考慮單個路徑。 它考慮了從源頭開始的所有路徑，并同時在所有這些路徑中向前移動了一個單元，這確保了第一次訪問目的地時，它是最短的路徑。 以下是該想法的實現– ## C++ ```cpp // C++ program to find the shortest path between // a given source cell to a destination cell. #include <bits/stdc++.h> using namespace std; #define ROW 9 #define COL 10 //To store matrix cell cordinates struct Point { ????int x; ????int y; }; // A Data Structure for queue used in BFS struct queueNode { ????Point pt;? // The cordinates of a cell ????int dist;? // cell's distance of from the source }; // check whether given cell (row, col) is a valid // cell or not. bool isValid(int row, int col) { ????// return true if row number and column number ????// is in range ????return (row >= 0) && (row < ROW) && ???????????(col >= 0) && (col < COL); } // These arrays are used to get row and column // numbers of 4 neighbours of a given cell int rowNum[] = {-1, 0, 0, 1}; int colNum[] = {0, -1, 1, 0}; // function to find the shortest path between // a given source cell to a destination cell. int BFS(int mat[][COL], Point src, Point dest) { ????// check source and destination cell ????// of the matrix have value 1 ????if (!mat[src.x][src.y] || !mat[dest.x][dest.y]) ????????return -1; ????bool visited[ROW][COL]; ????memset(visited, false, sizeof visited); ????// Mark the source cell as visited ????visited[src.x][src.y] = true; ????// Create a queue for BFS ????queue<queueNode> q; ????// Distance of source cell is 0 ????queueNode s = {src, 0}; ????q.push(s);? // Enqueue source cell ????// Do a BFS starting from source cell ????while (!q.empty()) ????{ ????????queueNode curr = q.front(); ????????Point pt = curr.pt; ????????// If we have reached the destination cell, ????????// we are done ????????if (pt.x == dest.x && pt.y == dest.y) ????????????return curr.dist; ????????// Otherwise dequeue the front cell in the queue ????????// and enqueue its adjacent cells ????????q.pop(); ????????for (int i = 0; i < 4; i++) ????????{ ????????????int row = pt.x + rowNum[i]; ????????????int col = pt.y + colNum[i]; ????????????// if adjacent cell is valid, has path and ????????????// not visited yet, enqueue it. ????????????if (isValid(row, col) && mat[row][col] &&? ???????????????!visited[row][col]) ????????????{ ????????????????// mark cell as visited and enqueue it ????????????????visited[row][col] = true; ????????????????queueNode Adjcell = { {row, col}, ??????????????????????????????????????curr.dist + 1 }; ????????????????q.push(Adjcell); ????????????} ????????} ????} ????// Return -1 if destination cannot be reached ????return -1; } // Driver program to test above function int main() { ????int mat[ROW][COL] = ????{ ????????{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 }, ????????{ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 }, ????????{ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 }, ????????{ 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 }, ????????{ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 }, ????????{ 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 }, ????????{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, ????????{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 }, ????????{ 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 } ????}; ????Point source = {0, 0}; ????Point dest = {3, 4}; ????int dist = BFS(mat, source, dest); ????if (dist != INT_MAX) ????????cout << "Shortest Path is " << dist ; ????else ????????cout << "Shortest Path doesn't exist"; ????return 0; } ```