Here we are going to solve the **maximum height of an elevation possible such that adjacent matrix cells have a difference of at most height 1**.

Please follow the steps,

Suppose 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**.

**Take an example:**

```
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}}
```

The above problem is going to solve **BFS** algorithm,

Follow the steps below to solve the problem:

- The first step initializes a 2d array,
**height**of size**M x N**to store the**final output matrix**. - The second step initializes a queue of pair,
**queue<pair<int, int>>q**to store the pair indexes for**BFS**. - In the third step traverse the matrix and mark the
**height**of the**land cell**as 0 and**enqueue**them,**also mark them as visited**. - In the fourth step perform
**BFS**:**Dequeue a cell from the 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 the current cell**.- Mark all the
**unvisited adjacent cell as visited**. - Repeat this
**unless the queue becomes empty**.

**Print the final height matrix**.

// 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 height void 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 & coloumn // 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 height void 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 Code int main() { // Given matrix int mat[][N] = { { 0, 0 }, { 0, 1 } }; // Function call to find // the matrix having // the maximum height findHeightMatrix(mat); return 0; }

**Output**

```
2 1 2
1 0 1
2 1 2
```

**Time Complexity:** **O(M * N) ****Auxiliary Space: O(M * N)**

Please comment and share this post and wants to improve and make a video about this article WhatsApp us.