本文概述

• CPP
• Java
• python

给定二进制网格*和初始位置。任务是找到从源到网格末端(第一行, 最后一行, 第一列或最后一列)的最小距离。可以移动到单元格网格[i] [j]除非网格[i] [j] = 0而且只有剩下, 对, up和下允许移动。如果不存在有效路径, 则打印-1.
例子：

输入：i = 1, j = 1, grid [] [] = {{1, 0, 1}, {0, 0, 0}, {1, 1, 1}}输出：1输入：i = 0, j = 0, grid [] [] = {{0, 1}, {1, 1}}输出：0

【从源到网格末端的最小距离】方法：

• 如果源已经是第一行/最后一行/列, 则打印0.
• 从开始使用源开始遍历网格BFS如下：
  • 在队列中插入单元格位置。
  • 从队列中弹出元素, 并将其标记为已访问。
  • 对于与弹出的相邻的每个有效步, 将单元格位置插入队列。
  • 每次移动时, 更新单元格到初始位置的最小距离。
• BFS完成后, 找到从源到第一行, 最后一行, 第一列和最后一列中每个单元的最小距离。
• 最后打印其中的最小值。

下面是上述方法的实现：
CPP

//C++ implementation of the approach #include < bits/stdc++.h> using namespace std; #define row 5 #define col 5//Global variables for grid, minDistance and visited array int minDistance[row + 1][col + 1], visited[row + 1][col + 1]; //Queue for BFS queue< pair< int , int> > que; //Function to find whether the move is valid or not bool isValid( int grid[][col], int i, int j) { if (i < 0 || j < 0 || j> = col || i> = row || grid[i][j] || visited[i][j]) return false ; return true ; }//Function to return the minimum distance //from source to the end of the grid int findMinPathminDistance( int grid[][col], int sourceRow, int sourceCol) { //If source is one of the destinations if (sourceCol == 0 || sourceCol == col - 1 || sourceRow == 0 || sourceRow == row - 1) return 0; //Set minimum value int minFromSource = row * col; //Precalculate minDistance of each grid with R * C for ( int i = 0; i < row; i++) for ( int j = 0; j < col; j++) minDistance[i][j] = row * col; //Insert source position in queue que.push(make_pair(sourceRow, sourceCol)); //Update minimum distance to visit source minDistance[sourceRow][sourceCol] = 0; //Set source to visited visited[sourceRow][sourceCol] = 1; //BFS approach for calculating the minDistance //of each cell from source while (!que.empty()) {//Iterate over all four cells adjacent //to current cell pair< int , int> cell = que.front(); //Initialize position of current cell int cellRow = cell.first; int cellCol = cell.second; //Cell below the current cell if (isValid(grid, cellRow + 1, cellCol)) {//Push new cell to the queue que.push(make_pair(cellRow + 1, cellCol)); //Update one of its neightbor's distance minDistance[cellRow + 1][cellCol] = min(minDistance[cellRow + 1][cellCol], minDistance[cellRow][cellCol] + 1); visited[cellRow + 1][cellCol] = 1; }//Above the current cell if (isValid(grid, cellRow - 1, cellCol)) { que.push(make_pair(cellRow - 1, cellCol)); minDistance[cellRow - 1][cellCol] = min(minDistance[cellRow - 1][cellCol], minDistance[cellRow][cellCol] + 1); visited[cellRow - 1][cellCol] = 1; }//Right cell if (isValid(grid, cellRow, cellCol + 1)) { que.push(make_pair(cellRow, cellCol + 1)); minDistance[cellRow][cellCol + 1] = min(minDistance[cellRow][cellCol + 1], minDistance[cellRow][cellCol] + 1); visited[cellRow][cellCol + 1] = 1; }//Left cell if (isValid(grid, cellRow, cellCol - 1)) { que.push(make_pair(cellRow, cellCol - 1)); minDistance[cellRow][cellCol - 1] = min(minDistance[cellRow][cellCol - 1], minDistance[cellRow][cellCol] + 1); visited[cellRow][cellCol - 1] = 1; }//Pop the visited cell que.pop(); }int i; //Minimum distance in the first row for (i = 0; i < col; i++) minFromSource = min(minFromSource, minDistance[0][i]); //Minimum distance in the last row for (i = 0; i < col; i++) minFromSource = min(minFromSource, minDistance[row - 1][i]); //Minimum distance in the first column for (i = 0; i < row; i++) minFromSource = min(minFromSource, minDistance[i][0]); //Minimum distance in the last column for (i = 0; i < row; i++) minFromSource = min(minFromSource, minDistance[i][col - 1]); //If no path exists if (minFromSource == row * col) return -1; //Return the minimum distance return minFromSource; }//Driver code int main() { int sourceRow = 3, sourceCol = 3; int grid[row][col] = { 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0 }; cout < < findMinPathminDistance(grid, sourceRow, sourceCol); return 0; }

Java

//Java implementation of the approach import java.util.*; class GFG {//Pair class static class Pair { int first, second; Pair( int a, int b) { first = a; second = b; } }static int row = 5 ; static int col = 5 ; //Global variables for grid, minDistance and visited array static int minDistance[][] = new int [row + 1 ][col + 1 ], visited[][] = new int [row + 1 ][col + 1 ]; //Queue for BFS static Queue< Pair> que= new LinkedList< > (); //Function to find whether the move is valid or not static boolean isValid( int grid[][], int i, int j) { if (i < 0 || j < 0 || j> = col || i> = row || grid[i][j] != 0 || visited[i][j] != 0 ) return false ; return true ; }//Function to return the minimum distance //from source to the end of the grid static int findMinPathminDistance( int grid[][], int sourceRow, int sourceCol) { //If source is one of the destinations if (sourceCol == 0 || sourceCol == col - 1 || sourceRow == 0 || sourceRow == row - 1 ) return 0 ; //Set minimum value int minFromSource = row * col; //Precalculate minDistance of each grid with R * C for ( int i = 0 ; i < row; i++) for ( int j = 0 ; j < col; j++) minDistance[i][j] = row * col; //Insert source position in queue que.add( new Pair(sourceRow, sourceCol)); //Update minimum distance to visit source minDistance[sourceRow][sourceCol] = 0 ; //Set source to visited visited[sourceRow][sourceCol] = 1 ; //BFS approach for calculating the minDistance //of each cell from source while (que.size()> 0 ) {//Iterate over all four cells adjacent //to current cell Pair cell = que.peek(); //Initialize position of current cell int cellRow = cell.first; int cellCol = cell.second; //Cell below the current cell if (isValid(grid, cellRow + 1 , cellCol)) {//add new cell to the queue que.add( new Pair(cellRow + 1 , cellCol)); //Update one of its neightbor's distance minDistance[cellRow + 1 ][cellCol] = Math.min(minDistance[cellRow + 1 ][cellCol], minDistance[cellRow][cellCol] + 1 ); visited[cellRow + 1 ][cellCol] = 1 ; }//Above the current cell if (isValid(grid, cellRow - 1 , cellCol)) { que.add( new Pair(cellRow - 1 , cellCol)); minDistance[cellRow - 1 ][cellCol] = Math.min(minDistance[cellRow - 1 ][cellCol], minDistance[cellRow][cellCol] + 1 ); visited[cellRow - 1 ][cellCol] = 1 ; }//Right cell if (isValid(grid, cellRow, cellCol + 1 )) { que.add( new Pair(cellRow, cellCol + 1 )); minDistance[cellRow][cellCol + 1 ] = Math.min(minDistance[cellRow][cellCol + 1 ], minDistance[cellRow][cellCol] + 1 ); visited[cellRow][cellCol + 1 ] = 1 ; }//Left cell if (isValid(grid, cellRow, cellCol - 1 )) { que.add( new Pair(cellRow, cellCol - 1 )); minDistance[cellRow][cellCol - 1 ] = Math.min(minDistance[cellRow][cellCol - 1 ], minDistance[cellRow][cellCol] + 1 ); visited[cellRow][cellCol - 1 ] = 1 ; }//Pop the visited cell que.remove(); }int i; //Minimum distance in the first row for (i = 0 ; i < col; i++) minFromSource = Math.min(minFromSource, minDistance[ 0 ][i]); //Minimum distance in the last row for (i = 0 ; i < col; i++) minFromSource = Math.min(minFromSource, minDistance[row - 1 ][i]); //Minimum distance in the first column for (i = 0 ; i < row; i++) minFromSource = Math.min(minFromSource, minDistance[i][ 0 ]); //Minimum distance in the last column for (i = 0 ; i < row; i++) minFromSource = Math.min(minFromSource, minDistance[i][col - 1 ]); //If no path exists if (minFromSource == row * col) return - 1 ; //Return the minimum distance return minFromSource; }//Driver code public static void main(String args[]) { int sourceRow = 3 , sourceCol = 3 ; int grid[][] = { { 1 , 1 , 1 , 1 , 0 }, { 0 , 0 , 1 , 0 , 1 }, { 0 , 0 , 1 , 0 , 1 }, { 1 , 0 , 0 , 0 , 1 }, { 1 , 1 , 0 , 1 , 0 }}; System.out.println(findMinPathminDistance(grid, sourceRow, sourceCol)); } }//This code is contributed by Arnab Kundu

python

# Python3 implementation of the approach from collections import deque as queue row = 5 col = 5# Global variables for grid, minDistance and visited array minDistance = [[ 0 for i in range (col + 1 )] for i in range (row + 1 )] visited = [[ 0 for i in range (col + 1 )] for i in range (row + 1 )]# Queue for BFS que = queue()# Function to find whether the move is valid or not def isValid(grid, i, j): if (i < 0 or j < 0 or j> = col or i> = row or grid[i][j] or visited[i][j]): return Falsereturn True# Function to return the minimum distance # from source to the end of the grid def findMinPathminDistance(grid, sourceRow, sourceCol):# If source is one of the destinations if (sourceCol = = 0 or sourceCol = = col - 1 or sourceRow = = 0 or sourceRow = = row - 1 ): return 0# Set minimum value minFromSource = row * col# Precalculate minDistance of each grid with R * C for i in range (row): for j in range (col): minDistance[i][j] = row * col# Insert source position in queue que.appendleft([sourceRow, sourceCol])# Update minimum distance to visit source minDistance[sourceRow][sourceCol] = 0 ; # Set source to visited visited[sourceRow][sourceCol] = 1 ; # BFS approach for calculating the minDistance # of each cell from source while ( len (que)> 0 ):# Iterate over all four cells adjacent # to current cell cell = que.pop()# Initialize position of current cell cellRow = cell[ 0 ] cellCol = cell[ 1 ]# Cell below the current cell if (isValid(grid, cellRow + 1 , cellCol)):# Push new cell to the queue que.appendleft([cellRow + 1 , cellCol])# Update one of its neightbor's distance minDistance[cellRow + 1 ][cellCol] = min (minDistance[cellRow + 1 ][cellCol], minDistance[cellRow][cellCol] + 1 ) visited[cellRow + 1 ][cellCol] = 1# Above the current cell if (isValid(grid, cellRow - 1 , cellCol)): que.appendleft([cellRow - 1 , cellCol]) minDistance[cellRow - 1 ][cellCol] = min (minDistance[cellRow - 1 ][cellCol], minDistance[cellRow][cellCol] + 1 ) visited[cellRow - 1 ][cellCol] = 1# Right cell if (isValid(grid, cellRow, cellCol + 1 )): que.appendleft([cellRow, cellCol + 1 ]) minDistance[cellRow][cellCol + 1 ] = min (minDistance[cellRow][cellCol + 1 ], minDistance[cellRow][cellCol] + 1 ) visited[cellRow][cellCol + 1 ] = 1 ; # Left cell if (isValid(grid, cellRow, cellCol - 1 )): que.appendleft([cellRow, cellCol - 1 ]) minDistance[cellRow][cellCol - 1 ] = min (minDistance[cellRow][cellCol - 1 ], minDistance[cellRow][cellCol] + 1 ) visited[cellRow][cellCol - 1 ] = 1# Pop the visited cell# Minimum distance in the first row for i in range (col): minFromSource = min (minFromSource, minDistance[ 0 ][i]); # Minimum distance in the last row for i in range (col): minFromSource = min (minFromSource, minDistance[row - 1 ][i]); # Minimum distance in the first column for i in range (row): minFromSource = min (minFromSource, minDistance[i][ 0 ]); # Minimum distance in the last column for i in range (row): minFromSource = min (minFromSource, minDistance[i][col - 1 ]); # If no path exists if (minFromSource = = row * col): return - 1# Return the minimum distance return minFromSource# Driver codesourceRow = 3 sourceCol = 3 grid = [[ 1 , 1 , 1 , 1 , 0 ], [ 0 , 0 , 1 , 0 , 1 ], [ 0 , 0 , 1 , 0 , 1 ], [ 1 , 0 , 0 , 0 , 1 ], [ 1 , 1 , 0 , 1 , 0 ]]print (findMinPathminDistance(grid, sourceRow, sourceCol))# This code is contributed by mohit kumar 29

输出如下：

2

推荐阅读

• 

  感冒可以戴隐形眼镜吗？
• 

  拼多多隐藏优惠券在哪里（拼多多隐藏优惠券怎么领）
• 

  如何在手机上使用云服务器的流量？ 手机怎么用云服务器的流量
• 

  使用log4j|使用log4j MDC实现日志追踪
• 

  贵宾犬价格
• 

  盒子刷安卓,机顶盒自动重启刷机需要用到什么东西?
• 

  网球场上的那些规则你真的了解吗？ 网球的规则
• 

  商品保管的意义和原则是什么
• 

  不要教育孩子应该怎么做 不想教育孩子怎么办
• 

  空调开睡眠模式半夜被热醒？ 空调睡眠模式是什么意思
• 

  鸽子粥的功效和作用
• 

  x60|为什么 2021 年的旗舰手机都需要满足这些关键词？
• 

  抖音怎么不让作品在同城显示 抖音作品怎么能不在同城显示
• 

  怎么上传优酷视频？优酷视频上传教程
• 

  怎么延长蜂蜜柠檬水的保质期
• 

  世界无烟日校园宣传标语大全 学校无烟日宣传标语
• 

  网友：2020年度高新区人才引进补贴逾半年未发放！
• 

  昆虫记中萤火虫的习性
• 

  Excel单元格怎么使用斜线一分为二？
• 

  电脑不读U盘怎么办

• 摩根大通公司面试经历|软件开发实习生
• Python–删除交替的连续重复项
• Python程序从文件中逐字符读取
• C++中的std::remove_cv用法示例介绍
• Python如何将字符串字典转换为字典（）
• 持久性系统面试经验（校园2021年批次）
• 难题（将一个正方形划分为N个较小的正方形）
• 算法设计（整数流中的模式(运行整数)）
• 深度技术光盘安装系统win8图文详细教程