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 visitedbool 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() functionint 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 codeimport 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 approachimport sys# User defined Pair classclass 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 visiteddef 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() functiondef 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 codemat = [[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 codeusing 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 classclass 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 visitedfunction 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() functionfunction 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 codelet 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.
- We LOOP till queue is not empty
- Dequeue front cell from the queue
- Return if the destination coordinates have been reached.
- 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 coordinatesstruct Point{ int x; int y;};// A Data Structure for queue used in BFSstruct 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 cellint 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 functionint 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 coordinatesstatic 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 BFSstatic 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 cellstatic 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 Codepublic 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 dequeROW = 9COL = 10# To store matrix cell coordinatesclass Point: def __init__(self,x: int, y: int): self.x = x self.y = y# A data structure for queue used in BFSclass 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 notdef 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 codedef 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 coordinatespublic 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 BFSpublic 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 cellstatic 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 Codepublic 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 = 9const COL = 10// To store matrix cell coordinatesclass Point{ constructor(x, y){ this.x = x this.y = y }}// A data structure for queue used in BFSclass 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 notfunction 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 celllet 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 codefunction 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)
This article is contributed by Aditya Goel. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
