Maximum height of an elevation possible such that adjacent matrix cells have a difference of at most height 1 | Java 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 ; Driver Code ; Given matrix ; Function call to find the matrix having the maximum height
import java . util . * ; class GFG { static final int M = 3 ; static final int N = 3 ; static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static void findHeightMatrixUtil ( int mat [ ] [ ] , int height [ ] [ ] ) { Queue < pair > q = new LinkedList < > ( ) ; int [ ] [ ] vis = new int [ M ] [ N ] ; for ( int i = 0 ; i < M ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { if ( mat [ i ] [ j ] == 1 ) { q . add ( new pair ( i , j ) ) ; height [ i ] [ j ] = 0 ; vis [ i ] [ j ] = 1 ; } } } while ( q . isEmpty ( ) == false ) { pair k = q . peek ( ) ; q . remove ( ) ; int x = k . first , y = k . second ; if ( x > 0 && vis [ x - 1 ] [ y ] == 0 ) { height [ x - 1 ] [ y ] = height [ x ] [ y ] + 1 ; vis [ x - 1 ] [ y ] = 1 ; q . add ( new pair ( 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 . add ( new pair ( 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 . add ( new pair ( 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 . add ( new pair ( x , y + 1 ) ) ; } } } static void findHeightMatrix ( int mat [ ] [ ] ) { int [ ] [ ] height = new int [ M ] [ N ] ; findHeightMatrixUtil ( mat , height ) ; for ( int i = 0 ; i < M ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) System . out . print ( height [ i ] [ j ] + " ▁ " ) ; System . out . println ( ) ; } } public static void main ( String [ ] args ) { int mat [ ] [ ] = { { 0 , 0 , 0 } , { 0 , 1 , 0 } , { 0 , 0 , 0 } } ; findHeightMatrix ( mat ) ; } }