Блог пользователя Satyam1104

Автор Satyam1104, история, 6 лет назад, По-английски

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;
}
  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 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.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
  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.