Zadanie Powódź XIV OI

Question

Mam problem z zadaniem Powódź, nie wiem, czemu dla większości testów wypluwa mi błąd. Zauważyłem, że optymalnymi kwadratami są zawsze najniżej położone punkty należące do Bajtocji, lecz coś musi być nie tak w mojj teorii. Pomógłby ktoś? Dzięki z góry :D

#include <iostream>
#include <cmath>
#include <queue>

using namespace std;

struct Wsp{
	int wart, x, y;

	bool operator < (const Wsp &wsp) const {
		return (wart > wsp.wart);
	}
};

struct Punkt2D {
	int x, y;
};

int X, Y, arr[1001][1001];
bool vis[1001][1001];
priority_queue <Wsp> wie;
queue <Punkt2D> q;

void bfs(int x, int y) {
	q.push({x, y});
	vis[x][y] = 1;
	while (!q.empty()) {
		x = q.front().x;
		y = q.front().y;
		q.pop();

		if (y - 1 >= 1 and abs(arr[x][y - 1]) >= abs(arr[x][y]) and !vis[x][y - 1]) {
			vis[x][y - 1] = 1;
			q.push({x, y - 1});
		} // gora
		if (y + 1 <= Y and abs(arr[x][y + 1]) >= abs(arr[x][y]) and !vis[x][y + 1]) {
			vis[x][y + 1] = 1;
			q.push({x, y + 1});
		} // dol
		if (x - 1 >= 1 and abs(arr[x - 1][y]) >= abs(arr[x][y]) and !vis[x - 1][y]) {
			vis[x - 1][y] = 1;
			q.push({x - 1, y});
		} // lewo
		if (x + 1 <= X and abs(arr[x + 1][y]) >= abs(arr[x][y]) and !vis[x + 1][y]) {
			vis[x + 1][y] = 1;
			q.push({x + 1, y});
		} // prawo
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> Y >> X;

	for (int y = 1; y <= Y; y ++) {
		for (int x = 1; x <= X; x ++) {
			cin >> arr[x][y];

			if (arr[x][y] > 0)
				wie.push({arr[x][y], x, y});
		}
	}

	int pompy = 0;
	while (!wie.empty()) {
		Wsp n = wie.top();
		wie.pop();
		
		if (!vis[n.x][n.y]) {
			// cout << n.x << ' ' << n.y << ' ' << n.wart << '\n';
			bfs(n.x, n.y);
			pompy ++;
		}
	}
	cout << pompy; // << '\n';

	/* for (int y = 1; y <= Y; y ++) {
		for (int x = 1; x <= X; x ++)
			cout << vis[x][y] << ' ';
		cout << '\n';
	} */
}

 

Comments

Pomysł jest poprawny, błąd jest gdzieś w implementacji. Możesz spróbować przeczytać rozwiązanie w ksiażeczce OI i spróbować zrozumieć jak to zaimplementować. Normalnie samemu bym to przeczytał, ale teraz nie mam czasu