Barbara got really good grades in school last year, so her parents decided to gift her with a pet rabbit. She was so excited that she built a house for the rabbit, which can be seen as a 2D grid with RR rows and CC columns. Rabbits love to jump, so Barbara stacked several boxes on several cells of the grid. Each box is a cube with equal dimensions, which match exactly the dimensions of a cell of the grid. However, Barbara soon realizes that it may be dangerous for the rabbit to make jumps of height greater than 11 box, so she decides to avoid that by making some adjustments to the house. For every pair of adjacent cells, Barbara would like that their absolute difference in height be at most 11 box. Two cells are considered adjacent if they share a common side. As all the boxes are superglued, Barbara cannot remove any boxes that are there initially, however she can add boxes on top of them. She can add as many boxes as she wants, to as many cells as she wants (which may be zero). Help her determine what is the minimum total number of boxes to be added so that the rabbit’s house is safe.
OR
Given a matrix of R rows and M columns. Make the absolute difference between the adjacent cells less than or equal to 1 by only increasing the cell value. The total increment done on cells should be minimized. The task is to return the minimum increment operations done.
Example:
Input: [[0 0 0],
[0 2 0],
[0 0 0]]
Output: 4
Explanation: the cell in the middle of the grid has an absolute difference in height of 2, the height of all its four adjacent cells is increased by exactly 1 unit so that the absolute difference between
any pair of adjacent cells will be at most 1. Resultant matrix will be:
[[0 1 0],
[1 2 1],
[0 1 0]]Input: [[1 0 5 4 2],
[1 5 6 4 8],
[2 3 4 2 1],
[2 3 4 9 8]]
Output: 52
Explanation: Resultant matrix will be: [[3 4 5 6 7],
[4 5 6 7 8 ],
[5 6 7 8 7],
[6 7 8 9 8]]
Approach: Given problem can be solved using multisource dijkstra’s algorithm. The approach is to store the cells with the largest values in a priority queue, pop out the priority queue one by one and update the adjacent cells accordingly, while updating the cell value we will also update our priority queue.
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach#include <bits/stdc++.h>using namespace std;void solve(long long int r, long long int c, vector<vector<long long int> >& grid){ priority_queue<pair<long long int, pair<long long int, long long int> > > pq; for (long long int i = 0; i < r; i++) { for (long long int j = 0; j < c; j++) { pq.push(make_pair(grid[i][j], make_pair(i, j))); } } long long int res = 0; while (!pq.empty()) { long long int height = pq.top().first, i = pq.top().second.first, j = pq.top().second.second; pq.pop(); if (height != grid[i][j]) continue; if (i == 0) { // Down if (i != r - 1) { if (grid[i + 1][j] < height - 1) { res += height - 1 - grid[i + 1][j]; grid[i + 1][j] = height - 1; pq.push(make_pair(height - 1, make_pair(i + 1, j))); } } // Left if (j != 0) { if (grid[i][j - 1] < height - 1) { res += height - 1 - grid[i][j - 1]; grid[i][j - 1] = height - 1; pq.push(make_pair(height - 1, make_pair(i, j - 1))); } } // Right if (j != c - 1) { if (grid[i][j + 1] < height - 1) { res += height - 1 - grid[i][j + 1]; grid[i][j + 1] = height - 1; pq.push(make_pair(height - 1, make_pair(i, j + 1))); } } } else if (i == r - 1) { // Up if (i != 0) { if (grid[i - 1][j] < height - 1) { res += height - 1 - grid[i - 1][j]; grid[i - 1][j] = height - 1; pq.push(make_pair(height - 1, make_pair(i - 1, j))); } } // Left if (j != 0) { if (grid[i][j - 1] < height - 1) { res += height - 1 - grid[i][j - 1]; grid[i][j - 1] = height - 1; pq.push(make_pair(height - 1, make_pair(i, j - 1))); } } // Right if (j != c - 1) { if (grid[i][j + 1] < height - 1) { res += height - 1 - grid[i][j + 1]; grid[i][j + 1] = height - 1; pq.push(make_pair(height - 1, make_pair(i, j + 1))); } } } else { // Down if (grid[i + 1][j] < height - 1) { res += height - 1 - grid[i + 1][j]; grid[i + 1][j] = height - 1; pq.push(make_pair(height - 1, make_pair(i + 1, j))); } // Up if (grid[i - 1][j] < height - 1) { res += height - 1 - grid[i - 1][j]; grid[i - 1][j] = height - 1; pq.push(make_pair(height - 1, make_pair(i - 1, j))); } // Left if (j != 0) { if (grid[i][j - 1] < height - 1) { res += height - 1 - grid[i][j - 1]; grid[i][j - 1] = height - 1; pq.push(make_pair(height - 1, make_pair(i, j - 1))); } } // Right if (j != c - 1) { if (grid[i][j + 1] < height - 1) { res += height - 1 - grid[i][j + 1]; grid[i][j + 1] = height - 1; pq.push(make_pair(height - 1, make_pair(i, j + 1))); } } } } cout << res;}// Driver codeint main(){ long long int r = 4, c = 5; vector<vector<long long int> > grid{ { 1, 0, 5, 4, 2 }, { 1, 5, 6, 4, 8 }, { 2, 3, 4, 2, 1 }, { 2, 3, 4, 9, 8 } }; solve(r, c, grid);} |
Python3
# Python program for the above approachfrom queue import PriorityQueuefrom typing import List, Tupledef solve(r: int, c: int, grid: List[List[int]]) -> int: pq = PriorityQueue() for i in range(r): for j in range(c): pq.put((grid[i][j], (i, j))) res = 0 while not pq.empty(): height, (i, j) = pq.get() if height != grid[i][j]: continue if i == 0: # Down if i != r - 1: if grid[i + 1][j] < height - 1: res += height - 1 - grid[i + 1][j] grid[i + 1][j] = height - 1 pq.put((height - 1, (i + 1, j))) # Left if j != 0: if grid[i][j - 1] < height - 1: res += height - 1 - grid[i][j - 1] grid[i][j - 1] = height - 1 pq.put((height - 1, (i, j - 1))) # Right if j != c - 1: if grid[i][j + 1] < height - 1: res += height - 1 - grid[i][j + 1] grid[i][j + 1] = height - 1 pq.put((height - 1, (i, j + 1))) elif i == r - 1: # Up if i != 0: if grid[i - 1][j] < height - 1: res += height - 1 - grid[i - 1][j] grid[i - 1][j] = height - 1 pq.put((height - 1, (i - 1, j))) # Left if j != 0: if grid[i][j - 1] < height - 1: res += height - 1 - grid[i][j - 1] grid[i][j - 1] = height - 1 pq.put((height - 1, (i, j - 1))) # Right if j != c - 1: if grid[i][j + 1] < height - 1: res += height - 1 - grid[i][j + 1] grid[i][j + 1] = height - 1 pq.put((height - 1, (i, j + 1))) else: # Down if grid[i + 1][j] < height - 1: res += height - 1 - grid[i + 1][j] grid[i + 1][j] = height - 1 pq.put((height - 1, (i + 1, j))) # Up if grid[i - 1][j] < height - 1: res += height - 1 - grid[i - 1][j] grid[i - 1][j] = height - 1 pq.put((height - 1, (i - 1, j))) # Left if j != 0: if grid[i][j - 1] < height - 1: res += height - 1 - grid[i][j - 1] grid[i][j - 1] = height - 1 pq.put((height - 1, (i, j - 1))) # Right if j != c - 1: if grid[i][j + 1] < height - 1: res += height - 1 - grid[i][j + 1] grid[i][j + 1] = height - 1 pq.put((height - 1, (i, j + 1))) return res# Example usager = 4c = 5grid = [[1, 0, 5, 4, 2], [1, 5, 6, 4, 8], [2, 3, 4, 2, 1], [2, 3, 4, 9, 8]]print(solve(r, c, grid)) # This code is contributed by Potta Lokesh |
Javascript
// JavaScript program for the above approachclass PriorityQueue { constructor() { this.queue = []; } enqueue(item) { let contain = false; for (let i = 0; i < this.queue.length; i++) { if (this.queue[i][0] > item[0]) { this.queue.splice(i, 0, item); contain = true; break; } } if (!contain) { this.queue.push(item); } } dequeue() { return this.queue.shift(); } isEmpty() { return this.queue.length === 0; }}function solve(r, c, grid) { const pq = new PriorityQueue(); for (let i = 0; i < r; i++) { for (let j = 0; j < c; j++) { pq.enqueue([grid[i][j], [i, j] ]); } } let res = 0; while (!pq.isEmpty()) { const [height, [i, j]] = pq.dequeue(); if (height != grid[i][j]) { continue; } if (i == 0) { // Down if (i != r - 1) { if (grid[i + 1][j] < height - 1) { res += height - 1 - grid[i + 1][j]; grid[i + 1][j] = height - 1; pq.enqueue([height - 1, [i + 1, j]]); } } // Left if (j != 0) { if (grid[i][j - 1] < height - 1) { res += height - 1 - grid[i][j - 1]; grid[i][j - 1] = height - 1; pq.enqueue([height - 1, [i, j - 1]]); } } // Right if (j != c - 1) { if (grid[i][j + 1] < height - 1) { res += height - 1 - grid[i][j + 1]; grid[i][j + 1] = height - 1; pq.enqueue([height - 1, [i, j + 1]]); } } } else if (i === r - 1) { // Up if (i !== 0) { if (grid[i - 1][j] < height - 1) { res += height - 1 - grid[i - 1][j]; grid[i - 1][j] = height - 1; pq.enqueue([height - 1, [i - 1, j]]); } } // Left if (j !== 0) { if (grid[i][j - 1] < height - 1) { res += height - 1 - grid[i][j - 1]; grid[i][j - 1] = height - 1; pq.enqueue([height - 1, [i, j - 1]]); } } // Right if (j !== c - 1) { if (grid[i][j + 1] < height - 1) { res += height - 1 - grid[i][j + 1]; grid[i][j + 1] = height - 1; pq.enqueue([height - 1, [i, j + 1]]); } } } else { // Down if (i + 1 < r && grid[i + 1][j] < height - 1) { res += height - 1 - grid[i + 1][j]; grid[i + 1][j] = height - 1; pq.enqueue([height - 1, [i + 1, j]]); } // Up if (i - 1 >= 0 && grid[i - 1][j] < height - 1) { res += height - 1 - grid[i - 1][j]; grid[i - 1][j] = height - 1; pq.enqueue([height - 1, [i - 1, j]]); } // Left if (j != 0 && grid[i][j - 1] < height - 1) { res += height - 1 - grid[i][j - 1]; grid[i][j - 1] = height - 1; pq.enqueue([height - 1, [i, j - 1]]); } // Right if (j != c - 1 && grid[i][j + 1] < height - 1) { res += height - 1 - grid[i][j + 1]; grid[i][j + 1] = height - 1; pq.enqueue([height - 1, [i, j + 1]]); } } } return res;}// Example usageconst r = 4;const c = 5;const grid = [ [1, 0, 5, 4, 2], [1, 5, 6, 4, 8], [2, 3, 4, 2, 1], [2, 3, 4, 9, 8]];console.log(solve(r, c, grid));// Contributed by adityasharmadev01 |
52
Time Complexity: O(RM * Log(RM))
Auxiliary Space: O(RM)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
