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 ; 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
using System ; using System . Collections . Generic ; class GFG { static int ROW ; static int COL ; class Point { public int x , y ; } ; static Point newPoint ( int x , int y ) { Point temp = new Point ( ) ; temp . x = x ; temp . y = y ; return temp ; } class Node { public Point pt ; public int dist ; } ; static Node newNode ( Point p , int dist ) { Node temp = new Node ( ) ; temp . pt = p ; temp . dist = dist ; return temp ; } static bool 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 i = 0 ; i < ROW ; i ++ ) { for ( int j = 0 ; j < COL ; j ++ ) d [ i , j ] = - 1 ; } d [ src . x , src . y ] = 0 ; bool [ , ] visited = new bool [ ROW , COL ] ; visited [ src . x , src . y ] = true ; Queue < Node > q = new Queue < Node > ( ) ; Node s = newNode ( src , 0 ) ; q . Enqueue ( s ) ; bool ok = false ; while ( q . Count > 0 ) { Node curr = q . Peek ( ) ; q . Dequeue ( ) ; 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 ) Console . Write ( pathmoves [ i ] ) ; ok = true ; break ; } if ( q . Count > 0 ) { q . Peek ( ) ; q . Dequeue ( ) ; } 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 = newNode ( newPoint ( row , col ) , curr . dist + 1 ) ; q . Enqueue ( adjCell ) ; d [ row , col ] = curr . dist + 1 ; } } } if ( ok == false ) Console . Write ( - 1 ) ; } public static void Main ( ) { char [ , ] mat = { { '0' , '1' , '0' , '1' } , { '1' , '0' , '1' , '1' } , { '0' , '1' , '1' , '1' } , { '1' , '1' , '1' , '0' } } ; ROW = mat . GetLength ( 0 ) ; COL = mat . GetLength ( 0 ) ; Point src = newPoint ( 0 , 3 ) ; Point dest = newPoint ( 3 , 0 ) ; pathMoves ( mat , src , dest ) ; } }