Open In App

Shortest path in a Binary Maze

Last Updated : 17 Mar, 2025
Suggest changes
Share
Like Article
Like
Report

Given an M x N 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.

Note: You can move into an adjacent cell in one of the four directions, Up, Down, Left, and Right if that adjacent cell is filled with element 1.

Example:

Input: mat[][] = [[1, 1, 1, 1], [1, 1, 0, 1], [1, 1, 1, 1], [1, 1, 0, 0], [1, 0, 0, 1]], source = [0, 1], destination = {2, 2}
Output: 3
Explanation: The path is (0, 1) -> (1, 1) -> (2, 1) - > (2, 2) (the same is highlighted below)
1 1 1 1
1 1 0 1
1 1 1 1
1 1 0 0
1 0 0 1

Input: mat[][] = [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 0 ] , [1, 0, 1, 0, 1]], source = {0, 0}, destination = {3, 4}
Output: -1
Explanation: The path is not possible between source and destination, hence return -1.

[Naive Approach] - Using DFS

The idea for this approach is to use Recursion to explore all possible paths at every step starting from the given source cell in the matrix and backtrack if the destination is not reached and also keep track of visited cells using an array.

C++ 
#include <bits/stdc++.h> 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 shortPath(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)) {  shortPath(mat, visited, i + 1, j, x, y, min_dist, dist + 1);  }    // go to the right cell  if (isSafe(mat, visited, i, j + 1)) {  shortPath(mat, visited, i, j + 1, x, y, min_dist, dist + 1);  }    // go to the top cell  if (isSafe(mat, visited, i - 1, j)) {  shortPath(mat, visited, i - 1, j, x, y, min_dist, dist + 1);  }    // go to the left cell  if (isSafe(mat, visited, i, j - 1)) {  shortPath(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 shortPath() function int shortPathLength(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;  shortPath(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 = shortPathLength(mat, src, dest);  cout << dist;    return 0; }
Java 
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 shortPath(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 = shortPath(mat, i + 1, j, x, y,  min_dist, dist + 1);  }  // go to the right cell  if (isSafe(mat, visited, i, j + 1)) {  min_dist = shortPath(mat, i, j + 1, x, y,  min_dist, dist + 1);  }  // go to the top cell  if (isSafe(mat, visited, i - 1, j)) {  min_dist = shortPath(mat, i - 1, j, x, y,  min_dist, dist + 1);  }  // go to the left cell  if (isSafe(mat, visited, i, j - 1)) {  min_dist = shortPath(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 shortPath() function  static int shortPathLength(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 = shortPath(mat, src[0], src[1],  dest[0], dest[1], dist, 0);  if (dist != Integer.MAX_VALUE)  return dist;  return -1;  }  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 = shortPathLength(mat, src, dest);  System.out.print(dist);  } }
Python 
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 shortPath(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 = shortPath( 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 = shortPath( 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 = shortPath( 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 = shortPath( 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 shortPath() function def shortPathLength(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 = shortPath(mat, visited, src.first, src.second, dest.first, dest.second, dist, 0) if (dist != sys.maxsize): return dist return -1 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 = shortPathLength(mat, src, dest) print(dist)
C# 
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 shortPath(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 = shortPath(mat, i + 1, j, x, y,  min_dist, dist + 1);  }  // go to the right cell  if (isSafe(mat, visited, i, j + 1)) {  min_dist = shortPath(mat, i, j + 1, x, y,  min_dist, dist + 1);  }  // go to the top cell  if (isSafe(mat, visited, i - 1, j)) {  min_dist = shortPath(mat, i - 1, j, x, y,  min_dist, dist + 1);  }  // go to the left cell  if (isSafe(mat, visited, i, j - 1)) {  min_dist = shortPath(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 shortPath() function  static int shortPathLength(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 = shortPath(mat, src[0], src[1],  dest[0], dest[1], dist, 0);  if (dist != Int32.MaxValue)  return dist;  return -1;  }  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 = shortPathLength(mat, src, dest);    Console.Write(dist);  } }
JavaScript 
// 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 shortPath(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  = shortPath(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  = shortPath(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  = shortPath(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  = shortPath(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 shortPath() function function shortPathLength(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 = shortPath(mat, visited, src.first,  src.second, dest.first,  dest.second, dist, 0);  if (dist != Number.MAX_SAFE_INTEGER)  return dist;  return -1; } 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 = shortPathLength(mat, src, dest); console.log(dist);

Output
11

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

[Expected Approach] - Using BFS

The idea for this approach is inspired from Lee algorithm and uses BFS.  The BFS 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.
We start from the source cell and call the BFS while maintaining a queue to store the coordinates of the matrix, and a Boolean array to keep track of the visited cells.

C++ 
#include <bits/stdc++.h> using namespace std; // A point in a Maze (Needed for QNode) struct Point {   int x, y;   Point(int x_, int y_) : x(x_), y(y_) {}  }; // A QNode (Needed for BFS) struct QNode {   Point p;   int d;   QNode(Point p_, int d_) : p(p_), d(d_) {}  }; bool isValid(int x, int y, int r, int c) {  return x >= 0 && x < r && y >= 0 && y < c; } int BFS(vector<vector<int>>& mat, Point src, Point dest) {  int r = mat.size(), c = mat[0].size();    // If Source and Destination are valid  if (!mat[src.x][src.y] || !mat[dest.x][dest.y]) return -1;  // Do BFS using Queue and Visited  vector<vector<bool>> vis(r, vector<bool>(c, false));  queue<QNode> q;  q.push(QNode(src, 0));  vis[src.x][src.y] = true;  while (!q.empty()) {    // Pop an item from queue  QNode node = q.front(); q.pop();  Point p = node.p;  int d = node.d;  // If we reached the destination  if (p.x == dest.x && p.y == dest.y) return d;    // Try all four adjacent  int dx[] = {-1, 0, 0, 1};  int dy[] = {0, -1, 1, 0};  for (int i = 0; i < 4; i++) {  int nx = p.x + dx[i], ny = p.y + dy[i];  if (isValid(nx, ny, r, c) && mat[nx][ny] && !vis[nx][ny]) {  vis[nx][ny] = true;  q.push(QNode(Point(nx, ny), d + 1));  }  }  }  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}  };  cout << BFS(mat, Point(0, 0), Point(3, 4)); }
Java 
// A point in a Maze (Needed for QNode) class Point {  int x, y;  Point(int x_, int y_) {  x = x_;  y = y_;  } } // A QNode (Needed for BFS) class QNode {  Point p;  int d;  QNode(Point p_, int d_) {  p = p_;  d = d_;  } } public class Maze {  static boolean isValid(int x, int y, int r, int c) {  return x >= 0 && x < r && y >= 0 && y < c;  }  static int BFS(int[][] mat, Point src, Point dest) {  int r = mat.length, c = mat[0].length;  // If Source and Destination are valid  if (mat[src.x][src.y] == 0 || mat[dest.x][dest.y] == 0) return -1;  // Do BFS using Queue and Visited  boolean[][] vis = new boolean[r][c];  java.util.Queue<QNode> q = new java.util.LinkedList<>();  q.add(new QNode(src, 0));  vis[src.x][src.y] = true;  while (!q.isEmpty()) {  // Pop an item from queue  QNode node = q.poll();  Point p = node.p;  int d = node.d;  // If we reached the destination  if (p.x == dest.x && p.y == dest.y) return d;  // Try all four adjacent  int[] dx = {-1, 0, 0, 1};  int[] dy = {0, -1, 1, 0};  for (int i = 0; i < 4; i++) {  int nx = p.x + dx[i], ny = p.y + dy[i];  if (isValid(nx, ny, r, c) && mat[nx][ny] == 1 && !vis[nx][ny]) {  vis[nx][ny] = true;  q.add(new QNode(new Point(nx, ny), d + 1));  }  }  }  return -1;  }  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}  };  System.out.println(BFS(mat, new Point(0, 0), new Point(3, 4)));  } }
Python 
# A point in a Maze (Needed for QNode) class Point: def __init__(self, x_, y_): self.x = x_ self.y = y_ # A QNode (Needed for BFS) class QNode: def __init__(self, p_, d_): self.p = p_ self.d = d_ def is_valid(x, y, r, c): return 0 <= x < r and 0 <= y < c def bfs(mat, src, dest): r, c = len(mat), len(mat[0]) # If Source and Destination are valid if not mat[src.x][src.y] or not mat[dest.x][dest.y]: return -1 # Do BFS using Queue and Visited vis = [[False] * c for _ in range(r)] from collections import deque q = deque([QNode(src, 0)]) vis[src.x][src.y] = True while q: # Pop an item from queue node = q.popleft() p = node.p d = node.d # If we reached the destination if p.x == dest.x and p.y == dest.y: return d # Try all four adjacent dx = [-1, 0, 0, 1] dy = [0, -1, 1, 0] for i in range(4): nx, ny = p.x + dx[i], p.y + dy[i] if is_valid(nx, ny, r, c) and mat[nx][ny] and not vis[nx][ny]: vis[nx][ny] = True q.append(QNode(Point(nx, ny), d + 1)) return -1 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] ] print(bfs(mat, Point(0, 0), Point(3, 4)))
C# 
// A point in a Maze (Needed for QNode) class Point {  public int x, y;  public Point(int x_, int y_) {  x = x_;  y = y_;  } } // A QNode (Needed for BFS) class QNode {  public Point p;  public int d;  public QNode(Point p_, int d_) {  p = p_;  d = d_;  } } public class Maze {  static bool IsValid(int x, int y, int r, int c) {  return x >= 0 && x < r && y >= 0 && y < c;  }  static int BFS(int[,] mat, Point src, Point dest) {  int r = mat.GetLength(0), c = mat.GetLength(1);  // If Source and Destination are valid  if (mat[src.x, src.y] == 0 || mat[dest.x, dest.y] == 0) return -1;  // Do BFS using Queue and Visited  bool[,] vis = new bool[r, c];  System.Collections.Generic.Queue<QNode> q = new System.Collections.Generic.Queue<QNode>();  q.Enqueue(new QNode(src, 0));  vis[src.x, src.y] = true;  while (q.Count > 0) {  // Pop an item from queue  QNode node = q.Dequeue();  Point p = node.p;  int d = node.d;  // If we reached the destination  if (p.x == dest.x && p.y == dest.y) return d;  // Try all four adjacent  int[] dx = {-1, 0, 0, 1};  int[] dy = {0, -1, 1, 0};  for (int i = 0; i < 4; i++) {  int nx = p.x + dx[i], ny = p.y + dy[i];  if (IsValid(nx, ny, r, c) && mat[nx, ny] == 1 && !vis[nx, ny]) {  vis[nx, ny] = true;  q.Enqueue(new QNode(new Point(nx, ny), d + 1));  }  }  }  return -1;  }  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}  };  System.Console.WriteLine(BFS(mat, new Point(0, 0), new Point(3, 4)));  } }
JavaScript 
// A point in a Maze (Needed for QNode) class Point {  constructor(x_, y_) {  this.x = x_;  this.y = y_;  } } // A QNode (Needed for BFS) class QNode {  constructor(p_, d_) {  this.p = p_;  this.d = d_;  } } function isValid(x, y, r, c) {  return x >= 0 && x < r && y >= 0 && y < c; } function BFS(mat, src, dest) {  const r = mat.length, c = mat[0].length;    // If Source and Destination are valid  if (!mat[src.x][src.y] || !mat[dest.x][dest.y]) return -1;  // Do BFS using Queue and Visited  const vis = Array.from({ length: r }, () => Array(c).fill(false));  const queue = [new QNode(src, 0)];  vis[src.x][src.y] = true;  while (queue.length > 0) {  // Pop an item from queue  const node = queue.shift();  const p = node.p;  const d = node.d;  // If we reached the destination  if (p.x === dest.x && p.y === dest.y) return d;    // Try all four adjacent  const dx = [-1, 0, 0, 1];  const dy = [0, -1, 1, 0];  for (let i = 0; i < 4; i++) {  const nx = p.x + dx[i], ny = p.y + dy[i];  if (isValid(nx, ny, r, c) && mat[nx][ny] && !vis[nx][ny]) {  vis[nx][ny] = true;  queue.push(new QNode(new Point(nx, ny), d + 1));  }  }  }  return -1; } const 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] ]; console.log(BFS(mat, new Point(0, 0), new Point(3, 4)));

Output
11

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


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

K

kartik

Similar Reads

Article Tags :
Practice Tags :
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy  Cookies are not collected in the GeeksforGeeks mobile applications.
Lightbox