给定一个N*M阶的矩阵。查找从源单元格到目标单元格的最短距离，只遍历有限的单元格。而且你只能上下左右移动。如果找到，则输出距离-1。 s代表“来源” d代表“目的地” *表示你可以旅行 0表示您不能旅行 这个问题是针对单一来源和目的地的。 例如：
null
Input : {'0', '*', '0', 's'}, {'*', '0', '*', '*'}, {'0', '*', '*', '*'}, {'d', '*', '*', '*'}Output : 6Input : {'0', '*', '0', 's'}, {'*', '0', '*', '*'}, {'0', '*', '*', '*'}, {'d', '0', '0', '0'}Output : -1
我们的想法是 BFS（广度优先搜索） 在基质细胞上。注意，如果图未加权，我们总是可以使用BFS来寻找最短路径。
- 将每个单元格存储为一个节点，包括它们的行、列值以及与源单元格的距离。
- 用源单元格启动BFS。
- 创建一个已访问的数组，其中除“0”单元格外的所有单元格都具有“假”值，因为“0”单元格被分配了“真”值，因为它们无法被遍历。
- 在每次移动中不断更新距离源值。
- 达到目的地时返回距离，否则返回-1（源和目的地之间不存在路径）。
CPP
// 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; } |
JAVA
/*package whatever //do not write package name here */ // Java Code implementation for above problem import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; // QItem for current location and distance // from source location class QItem { int row; int col; int dist; public QItem( int row, int col, int dist) { this .row = row; this .col = col; this .dist = dist; } } public class Maze { private static int minDistance( char [][] grid) { QItem source = new QItem( 0 , 0 , 0 ); // To keep track of visited QItems. Marking // blocked cells as visited. firstLoop: for ( int i = 0 ; i < grid.length; i++) { for ( int j = 0 ; j < grid[i].length; j++) { // Finding source if (grid[i][j] == 's' ) { source.row = i; source.col = j; break firstLoop; } } } // applying BFS on matrix cells starting from source Queue<QItem> queue = new LinkedList<>(); queue.add( new QItem(source.row, source.col, 0 )); boolean [][] visited = new boolean [grid.length][grid[ 0 ].length]; visited[source.row][source.col] = true ; while (queue.isEmpty() == false ) { QItem p = queue.remove(); // Destination found; if (grid[p.row][p.col] == 'd' ) return p.dist; // moving up if (isValid(p.row - 1 , p.col, grid, visited)) { queue.add( new QItem(p.row - 1 , p.col, p.dist + 1 )); visited[p.row - 1 ][p.col] = true ; } // moving down if (isValid(p.row + 1 , p.col, grid, visited)) { queue.add( new QItem(p.row + 1 , p.col, p.dist + 1 )); visited[p.row + 1 ][p.col] = true ; } // moving left if (isValid(p.row, p.col - 1 , grid, visited)) { queue.add( new QItem(p.row, p.col - 1 , p.dist + 1 )); visited[p.row][p.col - 1 ] = true ; } // moving right if (isValid(p.row, p.col + 1 , grid, visited)) { queue.add( new QItem(p.row, p.col + 1 , p.dist + 1 )); visited[p.row][p.col + 1 ] = true ; } } return - 1 ; } // checking where it's valid or not private static boolean isValid( int x, int y, char [][] grid, boolean [][] visited) { if (x >= 0 && y >= 0 && x < grid.length && y < grid[ 0 ].length && grid[x][y] != '0' && visited[x][y] == false ) { return true ; } return false ; } // Driver code public static void main(String[] args) { char [][] grid = { { '0' , '*' , '0' , 's' }, { '*' , '0' , '*' , '*' }, { '0' , '*' , '*' , '*' }, { 'd' , '*' , '*' , '*' } }; System.out.println(minDistance(grid)); } } // This code is contributed by abhikelge21. |
Python3
# Python3 Code implementation for above problem # QItem for current location and distance # from source location class QItem: def __init__( self , row, col, dist): self .row = row self .col = col self .dist = dist def __repr__( self ): return f "QItem({self.row}, {self.col}, {self.dist})" def minDistance(grid): source = QItem( 0 , 0 , 0 ) # Finding the source to start from for row in range ( len (grid)): for col in range ( len (grid[row])): if grid[row][col] = = 's' : source.row = row source.col = col break # To maintain location visit status visited = [[ False for _ in range ( len (grid[ 0 ]))] for _ in range ( len (grid))] # applying BFS on matrix cells starting from source queue = [] queue.append(source) visited[source.row][source.col] = True while len (queue) ! = 0 : source = queue.pop( 0 ) # Destination found; if (grid[source.row][source.col] = = 'd' ): return source.dist # moving up if isValid(source.row - 1 , source.col, grid, visited): queue.append(QItem(source.row - 1 , source.col, source.dist + 1 )) visited[source.row - 1 ][source.col] = True # moving down if isValid(source.row + 1 , source.col, grid, visited): queue.append(QItem(source.row + 1 , source.col, source.dist + 1 )) visited[source.row + 1 ][source.col] = True # moving left if isValid(source.row, source.col - 1 , grid, visited): queue.append(QItem(source.row, source.col - 1 , source.dist + 1 )) visited[source.row][source.col - 1 ] = True # moving right if isValid(source.row, source.col + 1 , grid, visited): queue.append(QItem(source.row, source.col + 1 , source.dist + 1 )) visited[source.row][source.col + 1 ] = True return - 1 # checking where move is valid or not def isValid(x, y, grid, visited): if ((x > = 0 and y > = 0 ) and (x < len (grid) and y < len (grid[ 0 ])) and (grid[x][y] ! = '0' ) and (visited[x][y] = = False )): return True return False # Driver code if __name__ = = '__main__' : grid = [[ '0' , '*' , '0' , 's' ], [ '*' , '0' , '*' , '*' ], [ '0' , '*' , '*' , '*' ], [ 'd' , '*' , '*' , '*' ]] print (minDistance(grid)) # This code is contributed by sajalmittaldei. |
Javascript
<script> // Javascript Code implementation for above problem var N = 4; var M = 4; // QItem for current location and distance // from source location class QItem { constructor(x, y, w) { this .row = x; this .col = y; this .dist = w; } }; function minDistance(grid) { var source = new QItem(0, 0, 0); // To keep track of visited QItems. Marking // blocked cells as visited. var visited = Array.from(Array(N), ()=>Array(M).fill(0)); for ( var i = 0; i < N; i++) { for ( var 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 var q = []; q.push(source); visited[source.row][source.col] = true ; while (q.length!=0) { var p = q[0]; q.shift(); // 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( new 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( new 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( new 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( new QItem(p.row, p.col + 1, p.dist + 1)); visited[p.row][p.col + 1] = true ; } } return -1; } // Driver code var grid = [ [ '0' , '*' , '0' , 's' ], [ '*' , '0' , '*' , '*' ], [ '0' , '*' , '*' , '*' ], [ 'd' , '*' , '*' , '*' ] ]; document.write(minDistance(grid)); // This code is contributed by rrrtnx. </script> |
输出
6
输出：
6
本文由 普拉尚特·辛格 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
