Satyam1104's blog

By Satyam1104, history, 3 years ago,

problem

[my code]

#include <bits/stdc++.h>
#define ll long long int
#define rep(i, a, n) for (ll i = a; i < n; i++)
#define ff first
#define ss second
#define endl '\n'

using namespace std;
void solve() {
ll n, m; cin >> n >> m;
ll g[n][m];
ll x, y, mx = 0;
queue<pair<ll, ll>>q;
ll vis[n][m];
rep(i, 0, n) {
rep(j, 0, m) {
cin >> g[i][j];
vis[i][j] = 0;
mx = max(mx, g[i][j]);
}
}
rep(i, 0, n) {
rep(j, 0, m) {
if (g[i][j] == mx) { vis[i][j] = 1; q.push({i, j});}
}
}

ll xx[4] = { -1, 0, 1, 0};
ll yy[4] = {0, 1, 0, -1};

ll ans = 0;
while (!q.empty()) {
x = q.front().ff;
y = q.front().ss;
q.pop();
rep(i, 0, 4) {
ll X = x + xx[i];
ll Y = y + yy[i];
if (X < 0 or Y <0 or Y > m - 1 or X > n - 1) continue;

if (!vis[X][Y]) {
if (g[X][Y] == g[x][y]) continue;
else {
if ((g[x][y] - g[X][Y]) == 1) {
q.push({X, Y});
vis[X][Y] = 1;
}
else if ((g[x][y] - g[X][Y]) > 1) {
vis[X][Y] = 1;
ans += (g[x][y] - g[X][Y]) - 1;
g[X][Y] = g[x][y] - 1;
q.push({X, Y});
}
}
}
}
}
cout << ans << endl;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin >> t;
rep(i, 1, t + 1)
{
cout << "Case #" << i << ": ";
solve();
}
return 0;
}

• -8