矩陣或網格中兩個單元之間的最短距離 · GeeksForGeeks 中文系列教程

# 矩陣或網格中兩個單元之間的最短距離 > 原文： [https://www.geeksforgeeks.org/shortest-distance-two-cells-matrix-grid/](https://www.geeksforgeeks.org/shortest-distance-two-cells-matrix-grid/) 給定一個 N * M 階矩陣。查找從源像元到目標像元的最短距離，僅遍歷有限的像元。您也只能向上，向下，向左和向右移動。如果找到，則輸出距離，否則為-1。 s 代表“源” d 代表“目的地” *代表您可以旅行的單元格 0 代表您不能旅行的單元格此問題僅適用于單個來源和目的地。例子： ``` Input : {'0', '*', '0', 's'}, {'*', '0', '*', '*'}, {'0', '*', '*', '*'}, {'d', '*', '*', '*'} Output : 6 Input : {'0', '*', '0', 's'}, {'*', '0', '*', '*'}, {'0', '*', '*', '*'}, {'d', '0', '0', '0'} Output : -1 ``` 這個想法是對矩陣單元進行 [BFS（優先搜索）](https://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/)。請注意，如果圖形未加權，我們總是可以使用 BFS 查找最短路徑。 1. 將每個單元格及其行，列值和到源單元格的距離存儲為節點。 2. 從源單元啟動 BFS。 3. 制作一個訪問數組，所有數組都具有“假”值，但不能遍歷被分配為“真”值的“ 0”單元格除外。 4. 每次移動時都要保持與源值的更新距離。 5. 到達目標位置時返回的距離，否則返回-1（源和目標之間不存在路徑）。 ``` // C++ Code implementation for above problem #include <bits/stdc++.h> using namespace std; #define N 4 #define M 4 // QItem for current location and distance // from source location class QItem { public: ????int row; ????int col; ????int dist; ????QItem(int x, int y, int w) ????????: row(x), col(y), dist(w) ????{ ????} }; int minDistance(char grid[N][M]) { ????QItem source(0, 0, 0); ????// To keep track of visited QItems. Marking ????// blocked cells as visited. ????bool visited[N][M]; ????for (int i = 0; i < N; i++) { ????????for (int j = 0; j < M; j++) ????????{ ????????????if (grid[i][j] == '0') ????????????????visited[i][j] = true; ????????????else ????????????????visited[i][j] = false; ????????????// Finding source ????????????if (grid[i][j] == 's') ????????????{ ???????????????source.row = i; ???????????????source.col = j; ????????????} ????????} ????} ????// applying BFS on matrix cells starting from source ????queue<QItem> q; ????q.push(source); ????visited[source.row][source.col] = true; ????while (!q.empty()) { ????????QItem p = q.front(); ????????q.pop(); ????????// Destination found; ????????if (grid[p.row][p.col] == 'd') ????????????return p.dist; ????????// moving up ????????if (p.row - 1 >= 0 && ????????????visited[p.row - 1][p.col] == false) { ????????????q.push(QItem(p.row - 1, p.col, p.dist + 1)); ????????????visited[p.row - 1][p.col] = true; ????????} ????????// moving down ????????if (p.row + 1 < N && ????????????visited[p.row + 1][p.col] == false) { ????????????q.push(QItem(p.row + 1, p.col, p.dist + 1)); ????????????visited[p.row + 1][p.col] = true; ????????} ????????// moving left ????????if (p.col - 1 >= 0 && ????????????visited[p.row][p.col - 1] == false) { ????????????q.push(QItem(p.row, p.col - 1, p.dist + 1)); ????????????visited[p.row][p.col - 1] = true; ????????} ?????????// moving right ????????if (p.col + 1 < M && ????????????visited[p.row][p.col + 1] == false) { ????????????q.push(QItem(p.row, p.col + 1, p.dist + 1)); ????????????visited[p.row][p.col + 1] = true; ????????} ????} ????return -1; } // Driver code int main() { ????char grid[N][M] = { { '0', '*', '0', 's' }, ????????????????????????{ '*', '0', '*', '*' }, ????????????????????????{ '0', '*', '*', '*' }, ????????????????????????{ 'd', '*', '*', '*' } }; ????cout << minDistance(grid); ????return 0; } ``` 輸出： ``` 6 ``` 本文由 [**Prashant Singh**](https://auth.geeksforgeeks.org/user/singhprashant/) 提供。如果您喜歡 GeeksforGeeks 并希望做出貢獻，則還可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。