Shortest path in a Binary Maze

Last Updated : 18 Nov, 2022

Given an MxN matrix where each element can either be 0 or 1. We need to find the shortest path between a given source cell to a destination cell. The path can only be created out of a cell if its value is 1.

Example:

Input:
mat[ROW][COL]  = {{1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
                  {1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
                  {1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
                  {0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
                  {1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
                  {1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
                  {1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
                  {1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
                  {1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }};
Source = {0, 0};
Destination = {3, 4};

Output:
Shortest Path is 11

Method 1: Using Backtracking

The idea is to use Recursion:

Start from the given source cell in the matrix and explore all four possible paths.
Check if the destination is reached or not.
Explore all the paths and backtrack if the destination is not reached.
And also keep track of visited cells using an array.

 Valid Moves are:
 left: (i, j) ——> (i, j – 1)
 right: (i, j) ——> (i, j + 1)
 top: (i, j) ——> (i - 1, j)
 bottom: (i, j) ——> (i + 1, j )

Implementation:

C++

#include <iostream>
#include <vector>
#include <climits>
#include <cstring>
using namespace std;
  
// Check if it is possible to go to (x, y) from the current position. The
// function returns false if the cell has value 0 or already visited
bool isSafe(vector<vector<int>> &mat, vector<vector<bool>> &visited, int x, int y)
{
    return (x >= 0 && x < mat.size() && y >= 0 && y < mat[0].size()) &&
            mat[x][y] == 1 && !visited[x][y];
}
  
  
void findShortestPath(vector<vector<int>> &mat, vector<vector<bool>> &visited,
                int i, int j, int x, int y, int &min_dist, int dist){
    if (i == x && j == y){
        min_dist = min(dist, min_dist);
        return;
    }
    // set (i, j) cell as visited
    visited[i][j] = true;
    // go to the bottom cell
    if (isSafe(mat, visited, i + 1, j)) {
        findShortestPath(mat, visited, i + 1, j, x, y, min_dist, dist + 1);
    }
    // go to the right cell
    if (isSafe(mat, visited, i, j + 1)) {
        findShortestPath(mat, visited, i, j + 1, x, y, min_dist, dist + 1);
    }
    // go to the top cell
    if (isSafe(mat, visited, i - 1, j)) {
        findShortestPath(mat, visited, i - 1, j, x, y, min_dist, dist + 1);
    }
    // go to the left cell
    if (isSafe(mat, visited, i, j - 1)) {
        findShortestPath(mat, visited, i, j - 1, x, y, min_dist, dist + 1);
    }
    // backtrack: remove (i, j) from the visited matrix
    visited[i][j] = false;
}
  
// Wrapper over findShortestPath() function
int findShortestPathLength(vector<vector<int>> &mat, pair<int, int> &src,
                    pair<int, int> &dest){
    if (mat.size() == 0 || mat[src.first][src.second] == 0 ||
            mat[dest.first][dest.second] == 0) 
        return -1;
     
    int row = mat.size();
    int col = mat[0].size();
    // construct an `M × N` matrix to keep track of visited cells
    vector<vector<bool>> visited;
    visited.resize(row, vector<bool>(col));
  
    int dist = INT_MAX;
    findShortestPath(mat, visited, src.first, src.second, dest.first, dest.second,
            dist, 0);
  
    if (dist != INT_MAX) 
        return dist;
    return -1;
}
  
int main()
{
    vector<vector<int>> mat =
    {{1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
                  {1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
                  {1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
                  {0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
                  {1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
                  {1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
                  {1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
                  {1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
                  {1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }};
  
    pair<int, int> src = make_pair(0, 0);
    pair<int, int> dest = make_pair(3, 4);
    int dist = findShortestPathLength(mat, src, dest);
    if (dist != -1)
        cout << "Shortest Path is " << dist;
     
    else
        cout << "Shortest Path doesn't exist";
   
    return 0;
}

Java

// Java implementation of the code
import java.util.*;
 
class GFG {
 
  static boolean[][] visited;
 
  // Check if it is possible to go to (x, y) from the
  // current position. The function returns false if the
  // cell has value 0 or already visited
  static boolean isSafe(int[][] mat, boolean[][] visited,
                        int x, int y)
  {
    return (x >= 0 && x < mat.length && y >= 0
            && y < mat[0].length && mat[x][y] == 1
            && !visited[x][y]);
  }
 
  static int findShortestPath(int[][] mat, int i, int j,
                              int x, int y, int min_dist,
                              int dist)
  {
 
    if (i == x && j == y) {
      min_dist = Math.min(dist, min_dist);
      return min_dist;
    }
 
    // set (i, j) cell as visited
    visited[i][j] = true;
    // go to the bottom cell
    if (isSafe(mat, visited, i + 1, j)) {
      min_dist = findShortestPath(mat, i + 1, j, x, y,
                                  min_dist, dist + 1);
    }
    // go to the right cell
    if (isSafe(mat, visited, i, j + 1)) {
      min_dist = findShortestPath(mat, i, j + 1, x, y,
                                  min_dist, dist + 1);
    }
    // go to the top cell
    if (isSafe(mat, visited, i - 1, j)) {
      min_dist = findShortestPath(mat, i - 1, j, x, y,
                                  min_dist, dist + 1);
    }
    // go to the left cell
    if (isSafe(mat, visited, i, j - 1)) {
      min_dist = findShortestPath(mat, i, j - 1, x, y,
                                  min_dist, dist + 1);
    }
    // backtrack: remove (i, j) from the visited matrix
    visited[i][j] = false;
    return min_dist;
  }
 
  // Wrapper over findShortestPath() function
  static int findShortestPathLength(int[][] mat,
                                    int[] src, int[] dest)
  {
    if (mat.length == 0 || mat[src[0]][src[1]] == 0
        || mat[dest[0]][dest[1]] == 0)
      return -1;
 
    int row = mat.length;
    int col = mat[0].length;
 
    // construct an `M × N` matrix to keep track of
    // visited cells
    visited = new boolean[row][col];
    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++)
        visited[i][j] = false;
    }
 
    int dist = Integer.MAX_VALUE;
    dist = findShortestPath(mat, src[0], src[1],
                            dest[0], dest[1], dist, 0);
 
    if (dist != Integer.MAX_VALUE)
      return dist;
    return -1;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int[][] mat = new int[][] {
      { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
      { 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
      { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
      { 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
      { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
      { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
      { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
      { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
      { 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }
    };
 
    int[] src = { 0, 0 };
    int[] dest = { 3, 4 };
    int dist = findShortestPathLength(mat, src, dest);
    if (dist != -1)
      System.out.print("Shortest Path is " + dist);
 
    else
      System.out.print("Shortest Path doesn't exist");
  }
}
 
// This code is contributed by phasing17

Python3

# Python3 code to implement the approach
import sys
 
# User defined Pair class
class Pair:
    def __init__(self, x, y):
        self.first = x
        self.second = y
 
# Check if it is possible to go to (x, y) from the current
# position. The function returns false if the cell has
# value 0 or already visited
def isSafe(mat, visited, x, y):
    return (x >= 0 and x < len(mat) and y >= 0 and y < len(mat[0]) and mat[x][y] == 1 and (not visited[x][y]))
 
def findShortestPath(mat, visited, i, j, x, y, min_dist, dist):
    if (i == x and j == y):
        min_dist = min(dist, min_dist)
        return min_dist
 
    # set (i, j) cell as visited
    visited[i][j] = True
     
    # go to the bottom cell
    if (isSafe(mat, visited, i + 1, j)):
        min_dist = findShortestPath(
            mat, visited, i + 1, j, x, y, min_dist, dist + 1)
 
    # go to the right cell
    if (isSafe(mat, visited, i, j + 1)):
        min_dist = findShortestPath(
            mat, visited, i, j + 1, x, y, min_dist, dist + 1)
 
    # go to the top cell
    if (isSafe(mat, visited, i - 1, j)):
        min_dist = findShortestPath(
            mat, visited, i - 1, j, x, y, min_dist, dist + 1)
 
    # go to the left cell
    if (isSafe(mat, visited, i, j - 1)):
        min_dist = findShortestPath(
            mat, visited, i, j - 1, x, y, min_dist, dist + 1)
 
    # backtrack: remove (i, j) from the visited matrix
    visited[i][j] = False
    return min_dist
 
# Wrapper over findShortestPath() function
def findShortestPathLength(mat, src, dest):
    if (len(mat) == 0 or mat[src.first][src.second] == 0
            or mat[dest.first][dest.second] == 0):
        return -1
 
    row = len(mat)
    col = len(mat[0])
 
    # construct an `M × N` matrix to keep track of visited
    # cells
    visited = []
    for i in range(row):
        visited.append([None for _ in range(col)])
 
    dist = sys.maxsize
    dist = findShortestPath(mat, visited, src.first,
                            src.second, dest.first, dest.second, dist, 0)
 
    if (dist != sys.maxsize):
        return dist
    return -1
 
# Driver code
mat = [[1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
       [1, 0, 1, 0, 1, 1, 1, 0, 1, 1],
       [1, 1, 1, 0, 1, 1, 0, 1, 0, 1],
       [0, 0, 0, 0, 1, 0, 0, 0, 0, 1],
       [1, 1, 1, 0, 1, 1, 1, 0, 1, 0],
       [1, 0, 1, 1, 1, 1, 0, 1, 0, 0],
       [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
       [1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
       [1, 1, 0, 0, 0, 0, 1, 0, 0, 1]
       ]
 
src = Pair(0, 0)
dest = Pair(3, 4)
dist = findShortestPathLength(mat, src, dest)
if (dist != -1):
    print("Shortest Path is", dist)
 
else:
    print("Shortest Path doesn't exist")
 
# This code is contributed by phasing17

C#

// C# implementation of the code
 
using System;
using System.Collections.Generic;
 
class GFG {
 
    static bool[, ] visited;
 
    // Check if it is possible to go to (x, y) from the
    // current position. The function returns false if the
    // cell has value 0 or already visited
    static bool isSafe(int[, ] mat, bool[, ] visited, int x,
                       int y)
    {
        return (x >= 0 && x < mat.GetLength(0) && y >= 0
                && y < mat.GetLength(1) && mat[x, y] == 1
                && !visited[x, y]);
    }
 
    static int findShortestPath(int[, ] mat, int i, int j,
                                int x, int y, int min_dist,
                                int dist)
    {
 
        if (i == x && j == y) {
            min_dist = Math.Min(dist, min_dist);
            return min_dist;
        }
 
        // set (i, j) cell as visited
        visited[i, j] = true;
        // go to the bottom cell
        if (isSafe(mat, visited, i + 1, j)) {
            min_dist = findShortestPath(mat, i + 1, j, x, y,
                                        min_dist, dist + 1);
        }
        // go to the right cell
        if (isSafe(mat, visited, i, j + 1)) {
            min_dist = findShortestPath(mat, i, j + 1, x, y,
                                        min_dist, dist + 1);
        }
        // go to the top cell
        if (isSafe(mat, visited, i - 1, j)) {
            min_dist = findShortestPath(mat, i - 1, j, x, y,
                                        min_dist, dist + 1);
        }
        // go to the left cell
        if (isSafe(mat, visited, i, j - 1)) {
            min_dist = findShortestPath(mat, i, j - 1, x, y,
                                        min_dist, dist + 1);
        }
        // backtrack: remove (i, j) from the visited matrix
        visited[i, j] = false;
        return min_dist;
    }
 
    // Wrapper over findShortestPath() function
    static int findShortestPathLength(int[, ] mat,
                                      int[] src, int[] dest)
    {
        if (mat.GetLength(0) == 0
            || mat[src[0], src[1]] == 0
            || mat[dest[0], dest[1]] == 0)
            return -1;
 
        int row = mat.GetLength(0);
        int col = mat.GetLength(1);
 
        // construct an `M × N` matrix to keep track of
        // visited cells
        visited = new bool[row, col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++)
                visited[i, j] = false;
        }
 
        int dist = Int32.MaxValue;
        dist = findShortestPath(mat, src[0], src[1],
                                dest[0], dest[1], dist, 0);
 
        if (dist != Int32.MaxValue)
            return dist;
        return -1;
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        int[, ] mat = new int[, ] {
            { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
            { 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
            { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
            { 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
            { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
            { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
            { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
            { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
            { 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }
        };
 
        int[] src = { 0, 0 };
        int[] dest = { 3, 4 };
        int dist = findShortestPathLength(mat, src, dest);
        if (dist != -1)
            Console.Write("Shortest Path is " + dist);
 
        else
            Console.Write("Shortest Path doesn't exist");
    }
}
 
// This code is contributed by phasing17

Javascript

// JavaScript code to implement the approach
 
 
// User defined Pair class
class Pair {
    constructor(x, y)
    {
        this.first = x;
        this.second = y;
    }
}
 
// Check if it is possible to go to (x, y) from the current
// position. The function returns false if the cell has
// value 0 or already visited
function isSafe(mat, visited, x, y)
{
    return (x >= 0 && x < mat.length && y >= 0
            && y < mat[0].length && mat[x][y] == 1
            && !visited[x][y]);
}
 
function findShortestPath(mat, visited, i, j, x, y,
                          min_dist, dist)
{
    if (i == x && j == y) {
        min_dist = Math.min(dist, min_dist);
        return min_dist;
    }
    // set (i, j) cell as visited
    visited[i][j] = true;
    // go to the bottom cell
    if (isSafe(mat, visited, i + 1, j)) {
        min_dist
            = findShortestPath(mat, visited, i + 1, j, x, y,
                               min_dist, dist + 1);
    }
    // go to the right cell
    if (isSafe(mat, visited, i, j + 1)) {
        min_dist
            = findShortestPath(mat, visited, i, j + 1, x, y,
                               min_dist, dist + 1);
    }
    // go to the top cell
    if (isSafe(mat, visited, i - 1, j)) {
        min_dist
            = findShortestPath(mat, visited, i - 1, j, x, y,
                               min_dist, dist + 1);
    }
    // go to the left cell
    if (isSafe(mat, visited, i, j - 1)) {
        min_dist
            = findShortestPath(mat, visited, i, j - 1, x, y,
                               min_dist, dist + 1);
    }
    // backtrack: remove (i, j) from the visited matrix
    visited[i][j] = false;
    return min_dist;
}
 
// Wrapper over findShortestPath() function
function findShortestPathLength(mat, src, dest)
{
    if (mat.length == 0 || mat[src.first][src.second] == 0
        || mat[dest.first][dest.second] == 0)
        return -1;
 
    let row = mat.length;
    let col = mat[0].length;
    // construct an `M × N` matrix to keep track of visited
    // cells
    let visited = [];
    for (var i = 0; i < row; i++)
        visited.push(new Array(col));
 
    let dist = Number.MAX_SAFE_INTEGER;
    dist = findShortestPath(mat, visited, src.first,
                            src.second, dest.first,
                            dest.second, dist, 0);
 
    if (dist != Number.MAX_SAFE_INTEGER)
        return dist;
    return -1;
}
 
// Driver code
 
let mat = [
    [ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 ],
    [ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 ],
    [ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 ],
    [ 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 ],
    [ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 ],
    [ 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 ],
    [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 ],
    [ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 ],
    [ 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 ]
];
 
let src = new Pair(0, 0);
let dest = new Pair(3, 4);
let dist = findShortestPathLength(mat, src, dest);
if (dist != -1)
    console.log("Shortest Path is " + dist);
 
else
    console.log("Shortest Path doesn't exist");
 
// This code is contributed by phasing17

Output

Shortest Path is 11

Time complexity: O(4^MN)
Auxiliary Space: O(M*N)

Method 2: Using BFS

The idea is inspired from Lee algorithm and uses BFS.

We start from the source cell and call the BFS procedure.
We maintain a queue to store the coordinates of the matrix and initialize it with the source cell.
We also maintain a Boolean array visited of the same size as our input matrix and initialize all its elements to false.
1. We LOOP till queue is not empty
2. Dequeue front cell from the queue
3. Return if the destination coordinates have been reached.
4. For each of its four adjacent cells, if the value is 1 and they are not visited yet, we enqueue it in the queue and also mark them as visited.

Note that BFS works here because it doesn’t consider a single path at once. It considers all the paths starting from the source and moves ahead one unit in all those paths at the same time which makes sure that the first time when the destination is visited, it is the shortest path.
Below is the implementation of the idea –

Implementation:

C++

// C++ program to find the shortest path between
// a given source cell to a destination cell.
#include <bits/stdc++.h>
using namespace std;
#define ROW 9
#define COL 10
 
//To store matrix cell coordinates
struct Point
{
    int x;
    int y;
};
 
// A Data Structure for queue used in BFS
struct queueNode
{
    Point pt;  // The coordinates of a cell
    int dist;  // cell's distance of from the source
};
 
// check whether given cell (row, col) is a valid
// cell or not.
bool isValid(int row, int col)
{
    // return true if row number and column number
    // is in range
    return (row >= 0) && (row < ROW) &&
           (col >= 0) && (col < COL);
}
 
// These arrays are used to get row and column
// numbers of 4 neighbours of a given cell
int rowNum[] = {-1, 0, 0, 1};
int colNum[] = {0, -1, 1, 0};
 
// function to find the shortest path between
// a given source cell to a destination cell.
int BFS(int mat[][COL], Point src, Point dest)
{
    // check source and destination cell
    // of the matrix have value 1
    if (!mat[src.x][src.y] || !mat[dest.x][dest.y])
        return -1;
 
    bool visited[ROW][COL];
    memset(visited, false, sizeof visited);
     
    // Mark the source cell as visited
    visited[src.x][src.y] = true;
 
    // Create a queue for BFS
    queue<queueNode> q;
     
    // Distance of source cell is 0
    queueNode s = {src, 0};
    q.push(s);  // Enqueue source cell
 
    // Do a BFS starting from source cell
    while (!q.empty())
    {
        queueNode curr = q.front();
        Point pt = curr.pt;
 
        // If we have reached the destination cell,
        // we are done
        if (pt.x == dest.x && pt.y == dest.y)
            return curr.dist;
 
        // Otherwise dequeue the front 
        // cell in the queue
        // and enqueue its adjacent cells
        q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int row = pt.x + rowNum[i];
            int col = pt.y + colNum[i];
             
            // if adjacent cell is valid, has path and
            // not visited yet, enqueue it.
            if (isValid(row, col) && mat[row][col] && 
               !visited[row][col])
            {
                // mark cell as visited and enqueue it
                visited[row][col] = true;
                queueNode Adjcell = { {row, col},
                                      curr.dist + 1 };
                q.push(Adjcell);
            }
        }
    }
 
    // Return -1 if destination cannot be reached
    return -1;
}
 
// Driver program to test above function
int main()
{
    int mat[ROW][COL] =
    {
        { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
        { 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
        { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
        { 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
        { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
        { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
        { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
        { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
        { 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }
    };
 
    Point source = {0, 0};
    Point dest = {3, 4};
 
    int dist = BFS(mat, source, dest);
 
    if (dist != -1)
        cout << "Shortest Path is " << dist ;
    else
        cout << "Shortest Path doesn't exist";
 
    return 0;
}

Java

// Java program to find the shortest 
// path between a given source cell 
// to a destination cell.
import java.util.*;
 
class GFG 
{
static int ROW = 9;
static int COL = 10;
 
// To store matrix cell coordinates
static class Point
{
    int x;
    int y;
 
    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
};
 
// A Data Structure for queue used in BFS
static class queueNode
{
    Point pt; // The coordinates of a cell
    int dist; // cell's distance of from the source
 
    public queueNode(Point pt, int dist)
    {
        this.pt = pt;
        this.dist = dist;
    }
};
 
// check whether given cell (row, col) 
// is a valid cell or not.
static boolean isValid(int row, int col)
{
    // return true if row number and 
    // column number is in range
    return (row >= 0) && (row < ROW) &&
           (col >= 0) && (col < COL);
}
 
// These arrays are used to get row and column
// numbers of 4 neighbours of a given cell
static int rowNum[] = {-1, 0, 0, 1};
static int colNum[] = {0, -1, 1, 0};
 
// function to find the shortest path between
// a given source cell to a destination cell.
static int BFS(int mat[][], Point src,
                            Point dest)
{
    // check source and destination cell
    // of the matrix have value 1
    if (mat[src.x][src.y] != 1 || 
        mat[dest.x][dest.y] != 1)
        return -1;
 
    boolean [][]visited = new boolean[ROW][COL];
     
    // Mark the source cell as visited
    visited[src.x][src.y] = true;
 
    // Create a queue for BFS
    Queue<queueNode> q = new LinkedList<>();
     
    // Distance of source cell is 0
    queueNode s = new queueNode(src, 0);
    q.add(s); // Enqueue source cell
 
    // Do a BFS starting from source cell
    while (!q.isEmpty())
    {
        queueNode curr = q.peek();
        Point pt = curr.pt;
 
        // If we have reached the destination cell,
        // we are done
        if (pt.x == dest.x && pt.y == dest.y)
            return curr.dist;
 
        // Otherwise dequeue the front cell 
        // in the queue and enqueue
        // its adjacent cells
        q.remove();
 
        for (int i = 0; i < 4; i++)
        {
            int row = pt.x + rowNum[i];
            int col = pt.y + colNum[i];
             
            // if adjacent cell is valid, has path 
            // and not visited yet, enqueue it.
            if (isValid(row, col) && 
                    mat[row][col] == 1 && 
                    !visited[row][col])
            {
                // mark cell as visited and enqueue it
                visited[row][col] = true;
                queueNode Adjcell = new queueNode
                             (new Point(row, col),
                                   curr.dist + 1 );
                q.add(Adjcell);
            }
        }
    }
 
    // Return -1 if destination cannot be reached
    return -1;
}
 
// Driver Code
public static void main(String[] args) 
{
    int mat[][] = {{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
                   { 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
                   { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
                   { 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
                   { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
                   { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
                   { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
                   { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
                   { 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }};
 
    Point source = new Point(0, 0);
    Point dest = new Point(3, 4);
 
    int dist = BFS(mat, source, dest);
 
    if (dist != -1)
        System.out.println("Shortest Path is " + dist);
    else
        System.out.println("Shortest Path doesn't exist");
    }
}
 
// This code is contributed by PrinciRaj1992

Python

# Python program to find the shortest
# path between a given source cell 
# to a destination cell.
 
from collections import deque
ROW = 9
COL = 10
 
# To store matrix cell coordinates
class Point:
    def __init__(self,x: int, y: int):
        self.x = x
        self.y = y
 
# A data structure for queue used in BFS
class queueNode:
    def __init__(self,pt: Point, dist: int):
        self.pt = pt  # The coordinates of the cell
        self.dist = dist  # Cell's distance from the source
 
# Check whether given cell(row,col)
# is a valid cell or not
def isValid(row: int, col: int):
    return (row >= 0) and (row < ROW) and
                   (col >= 0) and (col < COL)
 
# These arrays are used to get row and column 
# numbers of 4 neighbours of a given cell 
rowNum = [-1, 0, 0, 1]
colNum = [0, -1, 1, 0]
 
# Function to find the shortest path between 
# a given source cell to a destination cell. 
def BFS(mat, src: Point, dest: Point):
     
    # check source and destination cell 
    # of the matrix have value 1 
    if mat[src.x][src.y]!=1 or mat[dest.x][dest.y]!=1:
        return -1
     
    visited = [[False for i in range(COL)] 
                       for j in range(ROW)]
     
    # Mark the source cell as visited 
    visited[src.x][src.y] = True
     
    # Create a queue for BFS 
    q = deque()
     
    # Distance of source cell is 0
    s = queueNode(src,0)
    q.append(s) #  Enqueue source cell
     
    # Do a BFS starting from source cell 
    while q:
 
        curr = q.popleft() # Dequeue the front cell
         
        # If we have reached the destination cell, 
        # we are done 
        pt = curr.pt
        if pt.x == dest.x and pt.y == dest.y:
            return curr.dist
         
        # Otherwise enqueue its adjacent cells 
        for i in range(4):
            row = pt.x + rowNum[i]
            col = pt.y + colNum[i]
             
            # if adjacent cell is valid, has path  
            # and not visited yet, enqueue it.
            if (isValid(row,col) and
               mat[row][col] == 1 and
                not visited[row][col]):
                visited[row][col] = True
                Adjcell = queueNode(Point(row,col),
                                    curr.dist+1)
                q.append(Adjcell)
     
    # Return -1 if destination cannot be reached 
    return -1
 
# Driver code
def main():
    mat = [[ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 ],
           [ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 ], 
           [ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 ], 
           [ 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 ], 
           [ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 ], 
           [ 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 ], 
           [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 ], 
           [ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 ], 
           [ 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 ]]
    source = Point(0,0)
    dest = Point(3,4)
     
    dist = BFS(mat,source,dest)
     
    if dist!=-1:
        print("Shortest Path is",dist)
    else:
        print("Shortest Path doesn't exist")
main()
 
# This code is contributed by stutipathak31jan

C#

// C# program to find the shortest 
// path between a given source cell 
// to a destination cell.
using System;
using System.Collections.Generic;
 
class GFG 
{
static int ROW = 9;
static int COL = 10;
 
// To store matrix cell coordinates
public class Point
{
    public int x;
    public int y;
 
    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
};
 
// A Data Structure for queue used in BFS
public class queueNode
{
    // The coordinates of a cell
    public Point pt; 
     
    // cell's distance of from the source
    public int dist; 
 
    public queueNode(Point pt, int dist)
    {
        this.pt = pt;
        this.dist = dist;
    }
};
 
// check whether given cell (row, col) 
// is a valid cell or not.
static bool isValid(int row, int col)
{
    // return true if row number and 
    // column number is in range
    return (row >= 0) && (row < ROW) &&
           (col >= 0) && (col < COL);
}
 
// These arrays are used to get row and column
// numbers of 4 neighbours of a given cell
static int []rowNum = {-1, 0, 0, 1};
static int []colNum = {0, -1, 1, 0};
 
// function to find the shortest path between
// a given source cell to a destination cell.
static int BFS(int [,]mat, Point src,
                           Point dest)
{
    // check source and destination cell
    // of the matrix have value 1
    if (mat[src.x, src.y] != 1 || 
        mat[dest.x, dest.y] != 1)
        return -1;
 
    bool [,]visited = new bool[ROW, COL];
     
    // Mark the source cell as visited
    visited[src.x, src.y] = true;
 
    // Create a queue for BFS
    Queue<queueNode> q = new Queue<queueNode>();
     
    // Distance of source cell is 0
    queueNode s = new queueNode(src, 0);
    q.Enqueue(s); // Enqueue source cell
 
    // Do a BFS starting from source cell
    while (q.Count != 0)
    {
        queueNode curr = q.Peek();
        Point pt = curr.pt;
 
        // If we have reached the destination cell,
        // we are done
        if (pt.x == dest.x && pt.y == dest.y)
            return curr.dist;
 
        // Otherwise dequeue the front cell 
        // in the queue and enqueue
        // its adjacent cells
        q.Dequeue();
 
        for (int i = 0; i < 4; i++)
        {
            int row = pt.x + rowNum[i];
            int col = pt.y + colNum[i];
             
            // if adjacent cell is valid, has path 
            // and not visited yet, enqueue it.
            if (isValid(row, col) && 
                    mat[row, col] == 1 && 
               !visited[row, col])
            {
                // mark cell as visited and enqueue it
                visited[row, col] = true;
                queueNode Adjcell = new queueNode
                           (new Point(row, col),
                                curr.dist + 1 );
                q.Enqueue(Adjcell);
            }
        }
    }
 
    // Return -1 if destination cannot be reached
    return -1;
}
 
// Driver Code
public static void Main(String[] args) 
{
    int [,]mat = {{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
                  { 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
                   { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
                  { 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
                  { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
                  { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
                  { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
                  { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
                  { 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }};
 
    Point source = new Point(0, 0);
    Point dest = new Point(3, 4);
 
    int dist = BFS(mat, source, dest);
 
    if (dist != -1)
        Console.WriteLine("Shortest Path is " + dist);
    else
        Console.WriteLine("Shortest Path doesn't exist");
    }
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// JavaScript program to find the shortest
// path between a given source cell
// to a destination cell.
 
const ROW = 9
const COL = 10
 
// To store matrix cell coordinates
class Point{
    constructor(x, y){
        this.x = x
        this.y = y
    }
}
 
// A data structure for queue used in BFS
class queueNode{
    constructor(pt, dist){
        this.pt = pt // The coordinates of the cell
        this.dist = dist // Cell's distance from the source
    }
}
 
// Check whether given cell(row,col)
// is a valid cell or not
function isValid(row, col){
    return (row >= 0) && (row < ROW) &&
                (col >= 0) && (col < COL)
}
 
// These arrays are used to get row and column
// numbers of 4 neighbours of a given cell
let rowNum = [-1, 0, 0, 1]
let colNum = [0, -1, 1, 0]
 
// Function to find the shortest path between
// a given source cell to a destination cell.
function BFS(mat, src, dest){
     
    // check source and destination cell
    // of the matrix have value 1
    if(mat[src.x][src.y]!=1 || mat[dest.x][dest.y]!=1)
        return -1
     
    let visited = new Array(ROW).fill(false).map(()=>new Array(COL).fill(false));
     
    // Mark the source cell as visited
    visited[src.x][src.y] = true
     
    // Create a queue for BFS
    let q = []
     
    // Distance of source cell is 0
    let s = new queueNode(src,0)
    q.push(s) // Enqueue source cell
     
    // Do a BFS starting from source cell
    while(q){
 
        let curr = q.shift() // Dequeue the front cell
         
        // If we have reached the destination cell,
        // we are done
        let pt = curr.pt
        if(pt.x == dest.x && pt.y == dest.y)
            return curr.dist
         
        // Otherwise enqueue its adjacent cells
        for(let i=0;i<4;i++){
            let row = pt.x + rowNum[i]
            let col = pt.y + colNum[i]
             
            // if adjacent cell is valid, has path
            // and not visited yet, enqueue it.
            if (isValid(row,col) && mat[row][col] == 1 && !visited[row][col]){
                visited[row][col] = true
                let Adjcell = new queueNode(new Point(row,col),
                                    curr.dist+1)
                q.push(Adjcell)
            }
        }
    }
    // Return -1 if destination cannot be reached
    return -1
}
 
// Driver code
function main(){
     
let mat = [[ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 ],
        [ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 ],
        [ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 ],
        [ 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 ],
        [ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 ],
        [ 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 ],
        [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 ],
        [ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 ],
        [ 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 ]]
     
let source = new Point(0,0)
let dest = new Point(3,4)
     
let dist = BFS(mat,source,dest)
     
if(dist!=-1)
    document.write("Shortest Path is",dist,"</br>")
else
    document.write("Shortest Path doesn't exist","</br>")
}
 
main()
     
// This code is contributed by shinjanpatra
 
</script>

Output

Shortest Path is 11

Time complexity: O(M*N)
Auxiliary Space: O(M*N)

Suggest improvement

Minimum Cost Path in a directed graph via given set of intermediate nodes

Minimum cost to traverse from one index to another in the String

Share your thoughts in the comments

BFS in different language

Variations of BFS implementations

Easy problems on BFS

Intermediate problems on BFS

Hard Problems on BFS

BFS in different language

Variations of BFS implementations

Easy problems on BFS

Intermediate problems on BFS

Hard Problems on BFS

Shortest path in a Binary Maze

C++

Java

Python3

C#

Javascript

C++

Java

Python

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?