Minimum moves required to come out of a grid safely | C # program to implement the above approach ; Structure of cell of the grid ; Stores size of the grid ; 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 ; Function to check valid cells of the grid ; Checks for the border sides ; Driver Code ; Given grid
using System ; using System . Collections . Generic ; public class GFG { class pair { public int x , y ; public pair ( int x , int y ) { this . x = x ; this . y = y ; } } static int m , n ; static int minStep ( int [ , ] mat ) { m = mat . GetLength ( 0 ) ; n = mat . GetLength ( 1 ) ; int [ ] dx = { 1 , - 1 , 0 , 0 } ; int [ ] dy = { 0 , 0 , 1 , - 1 } ; Queue < pair > pQ = new Queue < pair > ( ) ; Queue < pair > fQ = new Queue < pair > ( ) ; for ( int i = 0 ; i < m ; i ++ ) for ( int j = 0 ; j < n ; j ++ ) { if ( mat [ i , j ] == 2 ) fQ . Enqueue ( new pair ( i , j ) ) ; else if ( mat [ i , j ] == 1 ) { if ( border ( i , j ) ) return 0 ; pQ . Enqueue ( new pair ( i , j ) ) ; } } int depth = 0 ; bool [ , ] visited = new bool [ n , m ] ; while ( pQ . Count != 0 ) { depth ++ ; for ( int i = pQ . Count ; i > 0 ; i -- ) { pair pos = pQ . Peek ( ) ; pQ . Dequeue ( ) ; if ( mat [ pos . x , pos . y ] == 2 ) continue ; for ( int j = 0 ; j < 4 ; j ++ ) { int x = pos . x + dx [ j ] ; int y = pos . y + dy [ j ] ; if ( valid ( x , y ) && mat [ x , y ] != 2 && ! visited [ x , y ] ) { visited [ x , y ] = true ; pQ . Enqueue ( new pair ( x , y ) ) ; if ( border ( x , y ) ) return depth ; } } } for ( int i = fQ . Count ; i > 0 ; i -- ) { pair pos = fQ . Peek ( ) ; fQ . Dequeue ( ) ; for ( int j = 0 ; j < 4 ; j ++ ) { int x = pos . x + dx [ j ] ; int y = pos . y + dy [ j ] ; if ( valid ( x , y ) && mat [ x , y ] != 2 ) { mat [ x , y ] = 2 ; fQ . Enqueue ( new pair ( x , y ) ) ; } } } } return - 1 ; } static bool valid ( int x , int y ) { return ( x >= 0 && x < m && y >= 0 && y < n ) ; } static bool border ( int x , int y ) { return ( x == 0 x == m - 1 y == 0 y == n - 1 ) ; } public static void Main ( String [ ] args ) { int [ , ] grid = { { 0 , 0 , 0 , 0 } , { 2 , 0 , 0 , 0 } , { 2 , 1 , 0 , 0 } , { 2 , 2 , 0 , 0 } } ; Console . WriteLine ( minStep ( grid ) ) ; } }