Shortest path from a source cell to a destination cell of a Binary Matrix through cells consisting only of 1 s | Java 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 ; Print 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
import java . io . * ; import java . lang . * ; import java . util . * ; class GFG { static int ROW ; static int COL ; static class Point { int x , y ; Point ( int x , int y ) { this . x = x ; this . y = y ; } } static class Node { Point pt ; int dist ; Node ( Point p , int dist ) { this . pt = p ; this . dist = dist ; } } static boolean isValid ( int row , int col ) { return ( row >= 0 ) && ( col >= 0 ) && ( row < ROW ) && ( col < COL ) ; } static int dRow [ ] = { - 1 , 0 , 0 , 1 } ; static int dCol [ ] = { 0 , - 1 , 1 , 0 } ; static void pathMoves ( char mat [ ] [ ] , Point src , Point dest ) { int d [ ] [ ] = new int [ ROW ] [ COL ] ; for ( int dd [ ] : d ) Arrays . fill ( dd , - 1 ) ; d [ src . x ] [ src . y ] = 0 ; boolean visited [ ] [ ] = new boolean [ ROW ] [ COL ] ; visited [ src . x ] [ src . y ] = true ; ArrayDeque < Node > q = new ArrayDeque < > ( ) ; Node s = new Node ( src , 0 ) ; q . addLast ( s ) ; boolean ok = false ; while ( ! q . isEmpty ( ) ) { Node curr = q . removeFirst ( ) ; 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 -- ; } for ( int i = pathmoves . length ( ) - 1 ; i >= 0 ; -- i ) System . out . print ( pathmoves . charAt ( i ) ) ; ok = true ; break ; } if ( ! q . isEmpty ( ) ) q . removeFirst ( ) ; 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 = new Node ( new Point ( row , col ) , curr . dist + 1 ) ; q . addLast ( adjCell ) ; d [ row ] [ col ] = curr . dist + 1 ; } } } if ( ! ok ) System . out . println ( - 1 ) ; } public static void main ( String [ ] args ) { char mat [ ] [ ] = { { '0' , '1' , '0' , '1' } , { '1' , '0' , '1' , '1' } , { '0' , '1' , '1' , '1' } , { '1' , '1' , '1' , '0' } } ; ROW = mat . length ; COL = mat [ 0 ] . length ; Point src = new Point ( 0 , 3 ) ; Point dest = new Point ( 3 , 0 ) ; pathMoves ( mat , src , dest ) ; } }