getting wrong answer
[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;
}
Use priority queue not queue and mathematically prove also why you will get correct ans by simulating popping and updating and pushing it neighbour element in priority queue if it isn't visited.
i think i am doing the same but without using priority queue
please let me know if i am wrong
"rep(i, 0, n) { rep(j, 0, m) { if (g[i][j] == mx) { vis[i][j] = 1; q.push({i, j});} } }"
You are only pushing the max element. There can be a matrix like n = 1, m = 5 || 9 8 7 2 1. Here you will push only 9 to the queue.
The second is priority queue or set erase.