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.