Shortest path from a source cell to a destination cell of a Binary Matrix through cells consisting only of 1 s | C ++ program for the above approach ; Stores the coordinates of the matrix cell ; Stores coordinates of a cell and its distance ; Check if the given cell is valid or not ; Stores the moves of the directions of adjacent cells ; Function to find the shortest path from the source to destination in the given matrix ; Stores the distance for each cell from the source cell ; Distance of source cell is 0 ; Initialize a visited array ; Mark source cell as visited ; Create a queue for BFS ; Distance of source cell is 0 ; Enqueue source cell ; Keeps track of whether destination is reached or not ; Iterate until queue is not empty ; Deque front of the queue ; If the destination cell is reached , then find the path ; Assign the distance of destination to the distance matrix ; Stores the smallest path ; Iterate until source is reached ; Append D ; Append U ; Append R ; Append L ; Reverse the backtracked path ; Pop the start of queue ; Explore all adjacent directions ; If the current cell is valid cell and can be traversed ; Mark the adjacent cells as visited ; Enque the adjacent cells ; Update the distance of the adjacent cells ; If the destination is not reachable ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ROW  4 NEW_LINE #define COL  4 NEW_LINE struct Point { int x , y ; } ; struct Node { Point pt ; int dist ; } ; bool isValid ( int row , int col ) { return ( row >= 0 ) && ( col >= 0 ) && ( row < ROW ) && ( col < COL ) ; } int dRow [ ] = { -1 , 0 , 0 , 1 } ; int dCol [ ] = { 0 , -1 , 1 , 0 } ; void pathMoves ( char mat [ ] [ COL ] , Point src , Point dest ) { int d [ ROW ] [ COL ] ; memset ( d , -1 , sizeof d ) ; d [ src . x ] [ src . y ] = 0 ; bool visited [ ROW ] [ COL ] ; memset ( visited , false , sizeof visited ) ; visited [ src . x ] [ src . y ] = true ; queue < Node > q ; Node s = { src , 0 } ; q . push ( s ) ; bool ok = false ; while ( ! q . empty ( ) ) { Node curr = q . front ( ) ; Point pt = curr . pt ; if ( pt . x == dest . x && pt . y == dest . y ) { int xx = pt . x , yy = pt . y ; int dist = curr . dist ; d [ pt . x ] [ pt . y ] = dist ; string pathmoves = " " ; while ( xx != src . x yy != src . y ) { if ( xx > 0 && d [ xx - 1 ] [ yy ] == dist - 1 ) { pathmoves += ' D ' ; xx -- ; } if ( xx < ROW - 1 && d [ xx + 1 ] [ yy ] == dist - 1 ) { pathmoves += ' U ' ; xx ++ ; } if ( yy > 0 && d [ xx ] [ yy - 1 ] == dist - 1 ) { pathmoves += ' R ' ; yy -- ; } if ( yy < COL - 1 && d [ xx ] [ yy + 1 ] == dist - 1 ) { pathmoves += ' L ' ; yy ++ ; } dist -- ; } reverse ( pathmoves . begin ( ) , pathmoves . end ( ) ) ; cout << pathmoves ; ok = true ; break ; } q . pop ( ) ; for ( int i = 0 ; i < 4 ; i ++ ) { int row = pt . x + dRow [ i ] ; int col = pt . y + dCol [ i ] ; if ( isValid ( row , col ) && ( mat [ row ] [ col ] == '1' mat [ row ] [ col ] == ' s ' mat [ row ] [ col ] == ' d ' ) && ! visited [ row ] [ col ] ) { visited [ row ] [ col ] = true ; Node adjCell = { { row , col } , curr . dist + 1 } ; q . push ( adjCell ) ; d [ row ] [ col ] = curr . dist + 1 ; } } } if ( ! ok ) cout << -1 ; } int main ( ) { char mat [ ROW ] [ COL ] = { { '0' , '1' , '0' , '1' } , { '1' , '0' , '1' , '1' } , { '0' , '1' , '1' , '1' } , { '1' , '1' , '1' , '0' } } ; Point src = { 0 , 3 } ; Point dest = { 3 , 0 } ; pathMoves ( mat , src , dest ) ; return 0 ; }