Check if a path exists for a cell valued 1 to reach the bottom right corner of a Matrix before any cell valued 2 | C ++ program for the above approach ; Function to check if cell with value 1 doesn 't reaches the bottom right cell or not ; Number of rows and columns ; Initialise the deque ; Traverse the matrix ; Push 1 to front of queue ; Push 2 to back of queue ; Store all the possible direction of the current cell ; Run multi - source BFS ; Get the front element ; Pop the front element ; If 1 reached corner first ; Insert new point in queue ; If 1 can 't reach the bottom  right then return false ; Driver Code ; Given matrix ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool reachesBottom ( vector < vector < int > > & a ) { int n = a . size ( ) ; int m = a [ 0 ] . size ( ) ; deque < vector < int > > q ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { if ( a [ i ] [ j ] == 1 ) { q . push_front ( { i , j , 1 } ) ; } else if ( a [ i ] [ j ] == 2 ) { q . push_back ( { i , j , 2 } ) ; } a [ i ] [ j ] = 0 ; } } int dx [ ] = { -1 , 0 , 1 , 0 } ; int dy [ ] = { 0 , 1 , 0 , -1 } ; while ( ! q . empty ( ) ) { auto front = q . front ( ) ; q . pop_front ( ) ; int i = front [ 0 ] , j = front [ 1 ] ; int t = front [ 2 ] ; if ( a [ i ] [ j ] ) continue ; a [ i ] [ j ] = 1 ; if ( t == 1 and ( i == n - 1 && j == m - 1 ) ) { return true ; } for ( int d = 0 ; d < 4 ; d ++ ) { int ni = i + dx [ d ] ; int nj = j + dy [ d ] ; if ( ni >= 0 and ni < n and nj > = 0 and nj < m ) { q . push_back ( { ni , nj , t } ) ; } } } return false ; } int main ( ) { vector < vector < int > > matrix { { 0 , 2 , 0 } , { 0 , 1 , 0 } , { 0 , 2 , 0 } } ; if ( reachesBottom ( matrix ) ) { cout << " YES " ; } else { cout << " NO " ; } return 0 ; }