KickStart A - Rabbit House

/**************************
*                         *
*    Author: Sukesh       *
*                         *
***************************/
#include<bits/stdc++.h>
#define FIO                 ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define int                 long long int
#define float               long double
#define re(arr, n, m)       arr.resize(n, vll (m,0))
#define inp1d(arr)          for(auto &it: arr) cin>>it
#define inp1ds(arr, sum)    for(auto &it: arr){ cin>>it; sum+=it; }
#define inp1dma(arr, m)     for(auto &it: arr){ cin>>it; m = max(m,it); }
#define inp1dmi(arr, m)     for(auto &it: arr){ cin>>it; m = min(m,it); }
#define inp2d(arr)          for(auto &it1: arr) for(auto &it2: it1) cin>>it2
#define o1d(arr)            for(auto it: arr) cout<<it<<" ";
#define o2d(arr)            for(auto it1: arr) { for(auto it2: it1) cout<<it2<<" "; cout<<endl; }
#define fo(i,s,e)           for(int i=s;i<e;i++)
#define fe(i,s,e)           for(int i=s;i<=e;i++)
#define fi(i,e,s)           for(int i=e;i>=s;i--)
#define vec(x)              vector<x>
#define mp(x,y)             map<x, y>
#define pr(x,y)             pair<x,y>
#define set(x)              set<x>
#define lb                  lower_bound
#define ub                  upper_bound
#define eb                  emplace_back
#define all(arr)            arr.begin(),arr.end()
#define S(arr)              arr.size()
#define nl                  cout<<"\n"
#define fr                  first
#define se                  second
#define contains(arr,x)     arr.find(x) != arr.end()
#define INF                 (int)1e9

using namespace std;
template<typename T,typename T1>T amax(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T amin(T &a,T1 b){if(b<a)a=b;return a;}

int di[] = {0,-1,0,1};
int dj[] = {1,0,-1,0};
vec(vec(int)) matrix;

bool isValid(int i, int j, int height){
    int n = S(matrix), m = S(matrix[0]);
    if(i<0 || j<0 || i>=n || j>=m)
        return 0;
    if(matrix[i][j] >= height-1)
        return 0;

    return 1;
}

int BFS(int i, int j){
    queue<pr(int,pr(int, int))> q;
    q.push({matrix[i][j], {i,j}});

    int ans = 0;
    while(!q.empty()){
        auto curr = q.front();
        q.pop();
        int height = curr.first;
        int x = curr.second.first, y = curr.second.second;

        fo(k,0,4){
            int nx = x + di[k], ny = y + dj[k];
            if(isValid(nx, ny, height)){
                int diff = height - 1 - matrix[nx][ny];
                ans += diff;
                matrix[nx][ny] += diff;
                q.push({matrix[nx][ny], {nx, ny}});
            }
        }
    }

    return ans;
}



int solve(){
    FIO;
    int r, c; cin >> r >> c;
    matrix.clear(), matrix.resize(r, vec(int) (c));

    int maxel = -1, maxi = 0, maxj = 0;
    fo(i,0,r){
        fo(j,0,c){
            cin >> matrix[i][j];
            if(matrix[i][j] > maxel){
                maxi = i, maxj = j;
                maxel = matrix[i][j];
            }
        }
    }

    int ans = BFS(maxi,maxj);
    fo(i,0,r){
        fo(j,0,c){
            ans += BFS(i,j);
        }
    }

    return ans;
}

signed main(){
    FIO;

    // #ifndef ONLINE_JUDGE
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // #endif

    int t=1;
    cin>>t;
    int n = t;
    while(t--){
        int res = solve();
        cout << "Case #" << n-t << ": " << res; nl;
    }

    #ifndef ONLINE_JUDGE
        cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    #endif
    return 0;
}