Minimum moves required to come out of a grid safely | ''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
m = 0 NEW_LINE n = 0 NEW_LINE def valid ( x , y ) : NEW_LINE INDENT global n NEW_LINE global m NEW_LINE return ( x >= 0 and x < m and y >= 0 and y < n ) NEW_LINE DEDENT def border ( x , y ) : NEW_LINE INDENT global n NEW_LINE global m NEW_LINE return ( x == 0 or x == m - 1 or y == 0 or y == n - 1 ) NEW_LINE DEDENT def minStep ( mat ) : NEW_LINE INDENT global n NEW_LINE global m NEW_LINE m = len ( mat ) NEW_LINE n = len ( mat [ 0 ] ) NEW_LINE dx = [ 1 , - 1 , 0 , 0 ] NEW_LINE dy = [ 0 , 0 , 1 , - 1 ] NEW_LINE pQ = [ ] NEW_LINE fQ = [ ] NEW_LINE for i in range ( m ) : NEW_LINE INDENT for j in range ( n ) : NEW_LINE INDENT if ( mat [ i ] [ j ] == 2 ) : NEW_LINE INDENT fQ . append ( [ i , j ] ) NEW_LINE DEDENT elif ( mat [ i ] [ j ] == 1 ) : NEW_LINE INDENT if ( border ( i , j ) ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT pQ . append ( [ i , j ] ) NEW_LINE DEDENT DEDENT DEDENT depth = 0 NEW_LINE visited = [ [ 0 for i in range ( m ) ] for j in range ( n ) ] NEW_LINE while ( len ( pQ ) > 0 ) : NEW_LINE INDENT depth += 1 NEW_LINE i = len ( pQ ) NEW_LINE while ( i > 0 ) : NEW_LINE INDENT pos = pQ [ 0 ] NEW_LINE pQ . remove ( pQ [ 0 ] ) NEW_LINE if ( mat [ pos [ 0 ] ] [ pos [ 1 ] ] == 2 ) : NEW_LINE INDENT continue NEW_LINE DEDENT for j in range ( 4 ) : NEW_LINE INDENT x = pos [ 0 ] + dx [ j ] NEW_LINE y = pos [ 1 ] + dy [ j ] NEW_LINE if ( valid ( x , y ) and mat [ x ] [ y ] != 2 and visited [ x ] [ y ] == 0 ) : NEW_LINE INDENT visited [ x ] [ y ] = 1 NEW_LINE pQ . append ( [ x , y ] ) NEW_LINE if ( border ( x , y ) ) : NEW_LINE INDENT return depth NEW_LINE DEDENT DEDENT DEDENT i -= 1 NEW_LINE DEDENT i = len ( fQ ) NEW_LINE while ( i > 0 ) : NEW_LINE INDENT pos = fQ [ 0 ] NEW_LINE fQ . remove ( fQ [ 0 ] ) NEW_LINE for j in range ( 4 ) : NEW_LINE INDENT x = pos [ 0 ] + dx [ j ] NEW_LINE y = pos [ 1 ] + dy [ j ] NEW_LINE if ( valid ( x , y ) and mat [ x ] [ y ] != 2 ) : NEW_LINE INDENT mat [ x ] [ y ] = 2 NEW_LINE fQ . append ( [ x , y ] ) NEW_LINE DEDENT DEDENT i -= 1 NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT grid = [ [ 0 , 0 , 0 , 0 ] , [ 2 , 0 , 0 , 0 ] , [ 2 , 1 , 0 , 0 ] , [ 2 , 2 , 0 , 0 ] ] NEW_LINE print ( minStep ( grid ) ) NEW_LINE DEDENT