Given a matrix mat][][] of size M x N which represents the topographic map of a region, and 0 denotes land and 1 denotes elevation, the task is to maximize the height in the matrix by assigning each cell a non-negative height such that the height of a land cell is 0 and two adjacent cells must have an absolute height difference of at most 1.
Examples:
Input: mat[][] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}
Output: {{0, 1, 2}, {1, 0, 1}, {2, 1, 0}}Input: mat[][] = {{0, 0, 1}, {1, 0, 0}, {0, 0, 0}}
Output: {{1, 1, 0}, {0, 1, 1}, {1, 2, 2}}
Approach: The idea is to use BFS. Follow the steps below to solve the problem:
- Initialize a 2d array, height of size M x N to store the final output matrix.
- Initialize a queue of pair, queue<pair<int, int>>q to store the pair indexes for BFS.
- Traverse the matrix and mark the height of land cell as 0 and enqueue them, also mark them as visited.
- Perform BFS:
- Dequeue a cell from queue and check all its 4 adjacent cells, if any of them is unvisited yet mark the height of this cell as 1 + height of current cell.
- Mark all the unvisited adjacent cell as visited.
- Repeat this unless the queue becomes empty.
- Print the final height matrix.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define M 3#define N 3// Utility function to find the matrix// having the maximum heightvoid findHeightMatrixUtil(int mat[][N], int height[M][N]){ // Stores index pairs for bfs queue<pair<int, int> > q; // Stores info about the visited cells int vis[M][N] = { 0 }; // Traverse the matrix 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; } } } // Breadth First Search while (q.empty() == 0) { pair<int, int> k = q.front(); q.pop(); // x & y are the row & column // of current cell int x = k.first, y = k.second; // 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) 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 }); } }}// Function to find the matrix having// the maximum heightvoid findHeightMatrix(int mat[][N]){ // Stores output matrix int height[M][N]; // Calling the helper function findHeightMatrixUtil(mat, height); // Print the final output matrix for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) cout << height[i][j] << " "; cout << endl; }}// Driver Codeint main(){ // Given matrix int mat[][N] = { { 0, 0 }, { 0, 1 } }; // Function call to find // the matrix having // the maximum height findHeightMatrix(mat); return 0;} |
Java
// Java program for the above approachimport 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; }} // Utility function to find the matrix// having the maximum heightstatic void findHeightMatrixUtil(int mat[][], int height[][]){ // Stores index pairs for bfs Queue<pair > q = new LinkedList<>(); // Stores info about the visited cells int [][]vis = new int[M][N]; // Traverse the matrix 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; } } } // Breadth First Search while (q.isEmpty() == false) { pair k = q.peek(); q.remove(); // x & y are the row & column // of current cell int x = k.first, y = k.second; // 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) 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 )); } }}// Function to find the matrix having// the maximum heightstatic void findHeightMatrix(int mat[][]){ // Stores output matrix int [][]height = new int[M][N]; // Calling the helper function findHeightMatrixUtil(mat, height); // Print the final output matrix for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) System.out.print(height[i][j]+ " "); System.out.println(); }}// Driver Codepublic static void main(String[] args){ // Given matrix int mat[][] = { { 0, 0,0 }, { 0, 1,0 },{ 0, 0,0 } }; // Function call to find // the matrix having // the maximum height findHeightMatrix(mat);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approachM = 3N = 3# Utility function to find the matrix# having the maximum heightdef findHeightMatrixUtil(mat, height): # Stores index pairs for bfs q = [] # Stores info about the visited cells vis = [[0 for i in range(N)]for j in range(M)] # Traverse the matrix for i in range(M): for j in range(N): if (mat[i][j] == 1): q.append([i, j]) height[i][j] = 0 vis[i][j] = 1 # Breadth First Search while (len(q) != 0): k = q[0] q = q[1:] # x & y are the row & column # of current cell x,y = k[0],k[1] # 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) if (x > 0 and vis[x - 1][y] == 0): height[x - 1][y] = height[x][y] + 1 vis[x - 1][y] = 1 q.append([x - 1, y]) if (y > 0 and vis[x][y - 1] == 0): height[x][y - 1] = height[x][y] + 1 vis[x][y - 1] = 1 q.append([x, y - 1]) if (x < M - 1 and vis[x + 1][y] == 0): height[x + 1][y] = height[x][y] + 1 vis[x + 1][y] = 1 q.append([x + 1, y]) if (y < N - 1 and vis[x][y + 1] == 0): height[x][y + 1] = height[x][y] + 1 vis[x][y + 1] = 1 q.append([x, y + 1]) return height# Function to find the matrix having# the maximum heightdef findHeightMatrix(mat): # Stores output matrix height = [[0 for i in range(N)]for j in range(M)] # Calling the helper function height = findHeightMatrixUtil(mat, height) # Print the final output matrix for i in range(M): for j in range(N): print(height[i][j] ,end = " ") print()# Driver Code# Given matrixmat = [ [ 0, 0,0], [0, 1,0 ],[0, 0,0 ]]# Function call to find# the matrix having# the maximum heightfindHeightMatrix(mat)# This code is contributed by shinjanpatra |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{static readonly int M = 3;static readonly int N = 3;class pair{ public int first, second; public pair(int first, int second) { this.first = first; this.second = second; }} // Utility function to find the matrix// having the maximum heightstatic void findHeightMatrixUtil(int [,]mat, int [,]height){ // Stores index pairs for bfs Queue<pair > q = new Queue<pair>(); // Stores info about the visited cells int [,]vis = new int[M,N]; // Traverse the matrix for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { if (mat[i,j] == 1) { q.Enqueue(new pair( i, j )); height[i,j] = 0; vis[i,j] = 1; } } } // Breadth First Search while (q.Count != 0 ) { pair k = q.Peek(); q.Dequeue(); // x & y are the row & column // of current cell int x = k.first, y = k.second; // 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) if (x > 0 && vis[x - 1, y] == 0) { height[x - 1, y] = height[x, y] + 1; vis[x - 1, y] = 1; q.Enqueue(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.Enqueue(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.Enqueue(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.Enqueue(new pair( x, y + 1 )); } }}// Function to find the matrix having// the maximum heightstatic void findHeightMatrix(int [,]mat){ // Stores output matrix int [,]height = new int[M, N]; // Calling the helper function findHeightMatrixUtil(mat, height); // Print the readonly output matrix for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) Console.Write(height[i,j]+ " "); Console.WriteLine(); }}// Driver Codepublic static void Main(String[] args){ // Given matrix int [,]mat = { { 0, 0,0 }, { 0, 1,0 },{ 0, 0,0 } }; // Function call to find // the matrix having // the maximum height findHeightMatrix(mat);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program for the above approachvar M = 3;var N = 3;// Utility function to find the matrix// having the maximum heightfunction findHeightMatrixUtil(mat, height){ // Stores index pairs for bfs var q = []; // Stores info about the visited cells var vis = Array.from(Array(M), ()=>Array(N).fill(0)); // Traverse the matrix 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; } } } // Breadth First Search while (q.length != 0) { var k = q[0]; q.shift(); // x & y are the row & column // of current cell var x = k[0], y = k[1]; // 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) 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 to find the matrix having// the maximum heightfunction findHeightMatrix(mat){ // Stores output matrix var height = Array.from(Array(M), ()=>Array(N).fill(0)); // Calling the helper function height = findHeightMatrixUtil(mat, height); // Print the final output matrix for (var i = 0; i < M; i++) { for (var j = 0; j < N; j++) document.write( height[i][j] + " "); document.write("<br>"); }}// Driver Code// Given matrixvar mat = [ [ 0, 0,0], [0, 1,0 ],[0, 0,0 ]];// Function call to find// the matrix having// the maximum heightfindHeightMatrix(mat);</script> |
Output:
2 1 2 1 0 1 2 1 2
Time Complexity: O(M * N)
Auxiliary Space: O(M * N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
