Maximum height of an elevation possible such that adjacent matrix cells have a difference of at most height 1 | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define M  3 NEW_LINE #define N  3 NEW_LINE void findHeightMatrixUtil ( int mat [ ] [ N ] , int height [ M ] [ N ] ) { queue < pair < int , int > > q ; int vis [ M ] [ N ] = { 0 } ; for ( int i = 0 ; i < M ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { if ( mat [ i ] [ j ] == 1 ) { q . push ( { i , j } ) ; height [ i ] [ j ] = 0 ; vis [ i ] [ j ] = 1 ; } } } while ( q . empty ( ) == 0 ) { pair < int , int > k = q . front ( ) ; q . pop ( ) ; 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 . 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 } ) ; } } } void findHeightMatrix ( int mat [ ] [ N ] ) { int height [ M ] [ N ] ; findHeightMatrixUtil ( mat , height ) ; for ( int i = 0 ; i < M ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) cout << height [ i ] [ j ] << " ▁ " ; cout << endl ; } } int main ( ) { int mat [ ] [ N ] = { { 0 , 0 } , { 0 , 1 } } ; findHeightMatrix ( mat ) ; return 0 ; }