Shortest path in a Binary Maze | Java program to find the shortest path between a given source cell to a destination cell . ; To store matrix cell cordinates ; A Data Structure for queue used in BFS ; The cordinates of a cell ; cell 's distance of from the source ; check whether given cell ( row , col ) is a valid cell or not . ; return true if row number and column number is in range ; These arrays are used to get row and column numbers of 4 neighbours of a given cell ; function to find the shortest path between a given source cell to a destination cell . ; check source and destination cell of the matrix have value 1 ; Mark the source cell as visited ; Create a queue for BFS ; Distance of source cell is 0 ; Enqueue source cell ; Do a BFS starting from source cell ; If we have reached the destination cell , we are done ; Otherwise dequeue the front cell in the queue and enqueue its adjacent cells ; if adjacent cell is valid , has path and not visited yet , enqueue it . ; mark cell as visited and enqueue it ; Return - 1 if destination cannot be reached ; Driver Code
import java . util . * ; class GFG { static int ROW = 9 ; static int COL = 10 ; static class Point { int x ; int y ; public Point ( int x , int y ) { this . x = x ; this . y = y ; } } ; static class queueNode { Point pt ; int dist ; public queueNode ( Point pt , int dist ) { this . pt = pt ; this . dist = dist ; } } ; static boolean isValid ( int row , int col ) { return ( row >= 0 ) && ( row < ROW ) && ( col >= 0 ) && ( col < COL ) ; } static int rowNum [ ] = { - 1 , 0 , 0 , 1 } ; static int colNum [ ] = { 0 , - 1 , 1 , 0 } ; static int BFS ( int mat [ ] [ ] , Point src , Point dest ) { if ( mat [ src . x ] [ src . y ] != 1 mat [ dest . x ] [ dest . y ] != 1 ) return - 1 ; boolean [ ] [ ] visited = new boolean [ ROW ] [ COL ] ; visited [ src . x ] [ src . y ] = true ; Queue < queueNode > q = new LinkedList < > ( ) ; queueNode s = new queueNode ( src , 0 ) ; q . add ( s ) ; while ( ! q . isEmpty ( ) ) { queueNode curr = q . peek ( ) ; Point pt = curr . pt ; if ( pt . x == dest . x && pt . y == dest . y ) return curr . dist ; q . remove ( ) ; for ( int i = 0 ; i < 4 ; i ++ ) { int row = pt . x + rowNum [ i ] ; int col = pt . y + colNum [ i ] ; if ( isValid ( row , col ) && mat [ row ] [ col ] == 1 && ! visited [ row ] [ col ] ) { visited [ row ] [ col ] = true ; queueNode Adjcell = new queueNode ( new Point ( row , col ) , curr . dist + 1 ) ; q . add ( Adjcell ) ; } } } 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 } } ; 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 " ) ; } }