Maximum height of an elevation possible such that adjacent matrix cells have a difference of at most height 1 | JavaScript program for the above approach ; Utility function to find the matrix having the maximum height ; Stores index pairs for bfs ; Stores info about the visited cells ; Traverse the matrix ; Breadth First Search ; x & y are the row & column of current cell ; Check all the 4 adjacent cells and marking them as visited if not visited yet also marking their height as 1 + height of cell ( x , y ) ; Function to find the matrix having the maximum height ; Stores output matrix ; Calling the helper function ; Print the final output matrix ; Given matrix ; Function call to find the matrix having the maximum height
var M = 3 ; var N = 3 ; function findHeightMatrixUtil ( mat , height ) { var q = [ ] ; var vis = Array . from ( Array ( M ) , ( ) => Array ( N ) . fill ( 0 ) ) ; for ( var i = 0 ; i < M ; i ++ ) { for ( var j = 0 ; j < N ; j ++ ) { if ( mat [ i ] [ j ] == 1 ) { q . push ( [ i , j ] ) ; height [ i ] [ j ] = 0 ; vis [ i ] [ j ] = 1 ; } } } while ( q . length != 0 ) { var k = q [ 0 ] ; q . shift ( ) ; var x = k [ 0 ] , y = k [ 1 ] ; if ( x > 0 && vis [ x - 1 ] [ y ] == 0 ) { height [ x - 1 ] [ y ] = height [ x ] [ y ] + 1 ; vis [ x - 1 ] [ y ] = 1 ; q . push ( [ x - 1 , y ] ) ; } if ( y > 0 && vis [ x ] [ y - 1 ] == 0 ) { height [ x ] [ y - 1 ] = height [ x ] [ y ] + 1 ; vis [ x ] [ y - 1 ] = 1 ; q . push ( [ x , y - 1 ] ) ; } if ( x < M - 1 && vis [ x + 1 ] [ y ] == 0 ) { height [ x + 1 ] [ y ] = height [ x ] [ y ] + 1 ; vis [ x + 1 ] [ y ] = 1 ; q . push ( [ x + 1 , y ] ) ; } if ( y < N - 1 && vis [ x ] [ y + 1 ] == 0 ) { height [ x ] [ y + 1 ] = height [ x ] [ y ] + 1 ; vis [ x ] [ y + 1 ] = 1 ; q . push ( [ x , y + 1 ] ) ; } } return height ; } function findHeightMatrix ( mat ) { var height = Array . from ( Array ( M ) , ( ) => Array ( N ) . fill ( 0 ) ) ; height = findHeightMatrixUtil ( mat , height ) ; for ( var i = 0 ; i < M ; i ++ ) { for ( var j = 0 ; j < N ; j ++ ) document . write ( height [ i ] [ j ] + " " ) ; document . write ( " " ) ; } } var mat = [ [ 0 , 0 , 0 ] , [ 0 , 1 , 0 ] , [ 0 , 0 , 0 ] ] ; findHeightMatrix ( mat ) ;