Given a binary grid of order r * c and an initial position. The task is to find the minimum distance from the source to get to the end of the grid (first row, last row, first column or last column). A move can be made to a cell grid[i][j] only if grid[i][j] = 0 and only left, right, up and down movements are permitted. If no valid path exists then print -1.
Examples:Â
Input: i = 1, j = 1, grid[][] = { {1, 0, 1}, {0, 0, 0}, {1, 1, 1}}Â
Output: 1Input: i = 0, j = 0, grid[][] = { {0, 1}, {1, 1}}Â
Output: 0Â
Approach:Â Â
- If source is already the first/last row/column then print 0.
- Start traversing the grid starting with source using BFS as :Â
- Insert cell position in queue.
- Pop element from queue and mark it visited.
- For each valid move adjacent to popped one, insert the cell position into queue.
- On each move, update the minimum distance of the cell from initial position.
- After the completion of the BFS, find the minimum distance from source to every cell in the first row, last row, first column and last column.
- Print the minimum among these in the end.
Below is the implementation of the above approach:Â Â
C++
// 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 arrayint minDistance[row + 1][col + 1], visited[row + 1][col + 1];Â
// Queue for BFSqueue<pair<int, int> > que;Â
// Function to find whether the move is valid or notbool 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 gridint 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 neighbor'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 codeint 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 approachimport java.util.*;class GFG{Â Â Â Â Â // Pair classstatic 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 arraystatic int minDistance[][] = new int[row + 1][col + 1], Â Â Â Â Â Â Â Â Â Â Â Â visited[][] = new int[row + 1][col + 1];Â
// Queue for BFSstatic Queue<Pair > que=new LinkedList<>();Â
// Function to find whether the move is valid or notstatic 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 gridstatic 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 neighbor'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 codepublic 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 |
Python3
# Python3 implementation of the approachfrom collections import deque as queuerow = 5col = 5Â
# Global variables for grid, minDistance and visited arrayminDistance = [[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 BFSque = queue()Â
# Function to find whether the move is valid or notdef 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 griddef 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 neighbor'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 = 3sourceCol = 3grid= [[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 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;Â
class GFG{Â Â Â Â Â // Pair classclass Pair{Â Â Â Â public int first, second;Â Â Â Â Â Â Â Â Â public Pair(int a, int b)Â Â Â Â {Â Â Â Â Â Â Â Â first = a;Â Â Â Â Â Â Â Â second = b;Â Â Â Â }}Â Â Â Â Â static int row = 5;static int col = 5;Â
// Global variables for grid, minDistance// and visited arraystatic int [,]minDistance = new int[row + 1, col + 1]; static int [,]visited = new int[row + 1, col + 1];Â
// Queue for BFSstatic Queue<Pair> que = new Queue<Pair>();Â
// Function to find whether the move is valid or notstatic bool 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 gridstatic 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;    int i = 0;         // Precalculate minDistance of each     // grid with R * C    for(i = 0; i < row; i++)        for(int j = 0; j < col; j++)            minDistance[i, j] = row * col;Â
    // Insert source position in queue    que.Enqueue(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.Count > 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.Enqueue(new Pair(cellRow + 1, cellCol));Â
            // Update one of its neighbor'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.Enqueue(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.Enqueue(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.Enqueue(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.Dequeue();    }         i = 0;Â
    // 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 codepublic 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 } };Â
    Console.WriteLine(findMinPathminDistance(        grid, sourceRow, sourceCol));}}Â
// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approachÂ
// Pair classclass Pair{Â Â Â Â constructor(a, b)Â Â Â Â {Â Â Â Â Â Â Â Â this.first = a;Â Â Â Â Â Â Â Â this.second = b;Â Â Â Â }}Â
let row = 5;let col = 5;Â
// Global variables for grid, minDistance and visited arraylet minDistance=new Array(row + 1);for(let i = 0; i < row + 1; i++){Â Â Â Â minDistance[i] = new Array(col+1);Â Â Â Â for(let j = 0; j < col + 1; j++)Â Â Â Â Â Â Â Â minDistance[i][j] = 0;}Â
let visited = new Array(row + 1);for(let i = 0; i < row + 1; i++){Â Â Â Â visited[i] = new Array(col + 1);Â Â Â Â for(let j = 0; j < col + 1; j++)Â Â Â Â Â Â Â Â visited[i][j] = 0;}Â
// Queue for BFSlet que = [];Â
// Function to find whether the move is valid or notfunction isValid(grid, i, 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 gridfunction findMinPathminDistance(grid,sourceRow,sourceCol){    // If source is one of the destinations    if (sourceCol == 0 || sourceCol == col - 1        || sourceRow == 0 || sourceRow == row - 1)        return 0;       // Set minimum value    let minFromSource = row * col;       // Precalculate minDistance of each grid with R * C    for (let i = 0; i < row; i++)        for (let j = 0; j < col; j++)            minDistance[i][j] = row * col;       // Insert source position in queue    que.push(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.length > 0)    {           // Iterate over all four cells adjacent        // to current cell        let cell = que[0];           // Initialize position of current cell        let cellRow = cell.first;        let cellCol = cell.second;           // Cell below the current cell        if (isValid(grid, cellRow + 1, cellCol))        {               // add new cell to the queue            que.push(new Pair(cellRow + 1, cellCol));               // Update one of its neighbor'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.push(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.push(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.push(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.shift();    }       let 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 codelet sourceRow = 3, sourceCol = 3;let 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 ]];document.write(findMinPathminDistance(grid,                             sourceRow, sourceCol));Â
// This code is contributed by avanitrachhadiya2155</script> |
2
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
