从源到网格末端的最小距离

2021年4月24日13:11:39 发表评论 751 次浏览

本文概述

给定二进制网格*和初始位置。任务是找到从源到网格末端(第一行, 最后一行, 第一列或最后一列)的最小距离。可以移动到单元格网格[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 False
  
     return 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 code
  
sourceRow = 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
木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: