Minimum moves required to come out of a grid safely | C ++ program to implement the above approach ; Stores size of the grid ; Function to check valid cells of the grid ; Checks for the border sides ; Function to find shortest distance between two cells of the grid ; Rows of the grid ; Column of the grid ; Stores possible move of the person ; Store possible cells visited by the person ; Store possible cells which are burning ; Traverse the grid ; If current cell is burning ; If person is in the current cell ; Stores shortest distance between two cells ; Check if a cell is visited by the person or not ; While pQ is not empty ; Update depth ; Popped all the cells from pQ and mark all adjacent cells of as visited ; Front element of the queue pQ ; Remove front element of the queue pQ ; If current cell is burning ; Find all adjacent cells ; Stores row number of adjacent cell ; Stores column number of adjacent cell ; Checks if current cell is valid ; Mark the cell as visited ; Enqueue the cell ; Checks the escape condition ; Burn all the adjacent cells of burning cells ; Front element of the queue fQ ; Delete front element of the queue fQ ; Find adjacent cells of burning cell ; Stores row number of adjacent cell ; Stores column number of adjacent cell ; Checks if current cell is valid ; Burn all the adjacent cells of current cell ; Driver Code ; Given grid
#include <bits/stdc++.h> NEW_LINE using namespace std ; int m , n ; bool valid ( int x , int y ) { return ( x >= 0 && x < m && y >= 0 && y < n ) ; } bool border ( int x , int y ) { return ( x == 0 x == m - 1 y == 0 y == n - 1 ) ; } int minStep ( vector < vector < int > > mat ) { m = mat . size ( ) ; n = mat [ 0 ] . size ( ) ; int dx [ ] = { 1 , -1 , 0 , 0 } ; int dy [ ] = { 0 , 0 , 1 , -1 } ; queue < pair < int , int > > pQ ; queue < pair < int , int > > fQ ; for ( int i = 0 ; i < m ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { if ( mat [ i ] [ j ] == 2 ) fQ . push ( { i , j } ) ; else if ( mat [ i ] [ j ] == 1 ) { if ( border ( i , j ) ) return 0 ; pQ . push ( { i , j } ) ; } } } int depth = 0 ; vector < vector < int > > visited ( n , vector < int > ( m , 0 ) ) ; while ( pQ . size ( ) > 0 ) { depth ++ ; for ( int i = pQ . size ( ) ; i > 0 ; i -- ) { pair < int , int > pos = pQ . front ( ) ; pQ . pop ( ) ; if ( mat [ pos . first ] [ pos . second ] == 2 ) continue ; for ( int j = 0 ; j < 4 ; j ++ ) { int x = pos . first + dx [ j ] ; int y = pos . second + dy [ j ] ; if ( valid ( x , y ) && mat [ x ] [ y ] != 2 && ! visited [ x ] [ y ] ) { visited [ x ] [ y ] = 1 ; pQ . push ( pair < int , int > ( x , y ) ) ; if ( border ( x , y ) ) return depth ; } } } for ( int i = fQ . size ( ) ; i > 0 ; i -- ) { pair < int , int > pos = fQ . front ( ) ; fQ . pop ( ) ; for ( int j = 0 ; j < 4 ; j ++ ) { int x = pos . first + dx [ j ] ; int y = pos . second + dy [ j ] ; if ( valid ( x , y ) && mat [ x ] [ y ] != 2 ) { mat [ x ] [ y ] = 2 ; fQ . push ( pair < int , int > ( x , y ) ) ; } } } } return -1 ; } int main ( ) { vector < vector < int > > grid = { { 0 , 0 , 0 , 0 } , { 2 , 0 , 0 , 0 } , { 2 , 1 , 0 , 0 } , { 2 , 2 , 0 , 0 } } ; cout << minStep ( grid ) ; }