Shortest path in a Binary Maze | C ++ 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 program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ROW  9 NEW_LINE #define COL  10 NEW_LINE struct Point { int x ; int y ; } ; struct queueNode { Point pt ; int dist ; } ; bool isValid ( int row , int col ) { return ( row >= 0 ) && ( row < ROW ) && ( col >= 0 ) && ( col < COL ) ; } int rowNum [ ] = { -1 , 0 , 0 , 1 } ; int colNum [ ] = { 0 , -1 , 1 , 0 } ; int BFS ( int mat [ ] [ COL ] , Point src , Point dest ) { if ( ! mat [ src . x ] [ src . y ] ! mat [ dest . x ] [ dest . y ] ) return -1 ; bool visited [ ROW ] [ COL ] ; memset ( visited , false , sizeof visited ) ; visited [ src . x ] [ src . y ] = true ; queue < queueNode > q ; queueNode s = { src , 0 } ; q . push ( s ) ; while ( ! q . empty ( ) ) { queueNode curr = q . front ( ) ; Point pt = curr . pt ; if ( pt . x == dest . x && pt . y == dest . y ) return curr . dist ; q . pop ( ) ; 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 ] && ! visited [ row ] [ col ] ) { visited [ row ] [ col ] = true ; queueNode Adjcell = { { row , col } , curr . dist + 1 } ; q . push ( Adjcell ) ; } } } return -1 ; } int main ( ) { int mat [ ROW ] [ COL ] = { { 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 = { 0 , 0 } ; Point dest = { 3 , 4 } ; int dist = BFS ( mat , source , dest ) ; if ( dist != -1 ) cout << " Shortest ▁ Path ▁ is ▁ " << dist ; else cout << " Shortest ▁ Path ▁ doesn ' t ▁ exist " ; return 0 ; }