# Maximum height of an elevation possible such that adjacent matrix cells have a difference of at most height 1

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.

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

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) 