Satyam1104's blog

By Satyam1104, history, 3 years ago, In English

getting wrong answer

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;
}
  • Vote: I like it
  • -8
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  1. You should always choose the maximum element at each step. and
  2. You are pushing into the queue only the maximum element. The difference greater than one need not be only near the maximum element.
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think i am doing the same but without using priority queue

    please let me know if i am wrong

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      "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.