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.

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