I hope you’re familiar with the problem.
What I have done:
I’ve used a priority queue and every time pop out the maximum element’s position from it and add (maximum element-1) to its neighbors if it’s absolute difference is greater than 1 from the maximum element and then push the neighbors. This process continues till the queue is empty.
Then I’ll add the difference between the original matrix and the box- added matrix to the answer.
But the problem is I’ve passed almost 90% of the test set but the output goes negative only when the input is exactly 50*50 (ie the size of the input matrix). I don’t know why. It’ll be helpful if somebody figured out the bug. I’ve spent some hours searching for the bug.
My_Code:
#include<iostream>
#include<vector>
#include<queue>
#include<climits>
#include<algorithm>
using namespace std;
int solve(vector<vector<long long>>& mat) {
priority_queue < pair<long long, pair<int, int>>> q;
long long ans = 0;
vector<vector<long long>> visited(mat.size(), vector<long long>(mat[0].size(), -1));
vector<vector<long long>> newMat(mat.size(),vector<long long>(mat[0].size(),0));
for (int r = 0; r < mat.size(); r++) {
for (int c = 0; c < mat[0].size(); c++) {
newMat[r][c] = mat[r][c];
q.push({ mat[r][c],{r,c} });
}
}
while (!q.empty()) {
pair<int, int> temp = q.top().second;
q.pop();
if(visited[temp.first][temp.second]==1)
continue;
else
visited[temp.first][temp.second] = 1;
long long dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
for (int i = 0; i < 4; i++) {
pair<int, int> p = temp;
p.first += dir[i][0];
p.second += dir[i][1];
if (p.first >= 0 && p.second < mat[0].size() && p.first < mat.size() && p.second >= 0 && visited[p.first][p.second] == -1) {
long long a = newMat[p.first][p.second];
long long b = newMat[temp.first][temp.second];
long long diff = (b - a);
if (diff >= 2) {
// ans += ((mat[temp.first][temp.second]-1) - (mat[p.first][p.second]));
newMat[p.first][p.second] = newMat[temp.first][temp.second] - 1;
q.push({newMat[p.first][p.second],{p.first,p.second}});
}
}
}
}
for(int i=0;i<mat.size();i++){
for(int j=0;j<mat[0].size();j++){
ans += (newMat[i][j]) - mat[i][j];
}
}
return ans;
}
void print(vector<vector<long long>>& mat) {
cout << "The matrix is: " << '\n';
for (auto i : mat) {
for (auto j : i) {
cout << j << " ";
}
cout << '\n';
}
}
int main() {
int t;
cin >> t;
for (int i = 0; i < t; i++) {
int row, col;
cin >> row >> col;
vector<vector<long long>> mat(row, vector<long long>(col, 0));
for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
cin >> mat[r][c];
}
}
long long ans = solve(mat);
cout << "Case #" << (i + 1) << ": " << ans << '\n';
}
return 0;
}
Here’s the solution which is exactly the same logic as my above program solution which passes all the test cases. Both are exactly the same logic but slightly different code. You can use it to test my program’s bug.
// RABBIT HOUSE
// TIME COMPLEXITY:- O(R*C*log(R*C))
// SPACE COMPLEXITY:- O(R*C*log(R*C))
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define vi vector<ll>
#define pb push_back
#define F first
#define S second
#define all(v) (v).begin(),(v).end()
#define pii pair<ll,ll>
#define vii vector<pii>
#define calc_fact(n) tgamma(n+1)
#define inf LONG_LONG_MAX
#define MOD 1000000007
#define mod 998244353
ll solve()
{
ll n,m;
cin>>n>>m;
vector<vi> mat(n,vi(m,0));
vector<vi> original(n,vi(m,0));
// visited matrix
vector<vector<bool>> visited(n,vector<bool>(m,false));
// maximum heap
priority_queue<pair<ll,pii>> q;
for(ll i=0;i<n;i++)
{
for(ll j=0;j<m;j++)
{
cin>>mat[i][j];
original[i][j] = mat[i][j];
// push all the elements in the priority queue
q.push({mat[i][j],{i,j}});
}
}
ll ans = 0;
while(!q.empty())
{
ll val = q.top().F;
ll x = q.top().S.F;
ll y = q.top().S.S;
q.pop();
if(visited[x][y])
{
continue;
}
visited[x][y] = true;
if(x+1<n and !visited[x+1][y])
{
ll diff = mat[x][y]-mat[x+1][y];
if(diff>1)
{
mat[x+1][y] = mat[x][y]-1;
q.push({mat[x+1][y],{x+1,y}});
}
}
if(x-1>=0 and !visited[x-1][y])
{
ll diff = mat[x][y]-mat[x-1][y];
if(diff>1)
{
mat[x-1][y] = mat[x][y]-1;
q.push({mat[x-1][y],{x-1,y}});
}
}
if(y+1<m and !visited[x][y+1])
{
ll diff = mat[x][y]-mat[x][y+1];
if(diff>1)
{
mat[x][y+1] = mat[x][y]-1;
q.push({mat[x][y+1],{x,y+1}});
}
}
if(y-1>=0 and !visited[x][y-1])
{
ll diff = mat[x][y]-mat[x][y-1];
if(diff>1)
{
mat[x][y-1] = mat[x][y]-1;
q.push({mat[x][y-1],{x,y-1}});
}
}
}
// minimum answer will be number of stacks added for every cell
for(ll i=0;i<n;i++)
{
for(ll j=0;j<m;j++)ans+=(mat[i][j]-original[i][j]);
}
return ans;
}
signed main()
{
FIO;
ll t;
cin>>t;
for(ll i=1;i<=t;i++)
{
cout<<"Case #"<<i<<": ";
cout<<solve()<<endl;
}
}