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

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

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

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

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

    please let me know if i am wrong

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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