Mam takie zadanie:
Bajtocy posiada spory teren lasu podzielony na n × n kwadratowych pól (ułożonych po n wierszy i n kolumn). Na każdym polu rośnie dokładnie jedno drzewo. Możemy założyć, że znamy wiek każdego drzewa. Bajtocy chce zbudować dom składający się z d kwadratowych pól, jednak w tym celu musi wyciąć część swoich drzew (dokładnie d drzew). Zakładamy, że dom powinien być spójny, czyli z każdego miejsca w domu powinno dać się dojść do każdego innego miejsca. Pomóż Bajtocemu wybrać miejsce budowy domu, tak aby najstarsze drzewo ze wszystkich wyciętych było możliwie najmłodsze.
Wejście
W pierwszym wierszu wejścia są dwie liczby całkowite n i d (1 <= d <= n <= 1 000) oznaczające odpowiednio wielkość terenu oraz rozmiar domu, który chce zbudować Bajtocy. Kolejnych n wierszy zawiera po n liczb całkowitych wi,k (1 <= wi,k <= 10^9) oznaczających wiek drzewa rosnącego na polu w i-tym wierszu i k-tej kolumnie.
Wyjście
Jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą równą minimalnemu wiekowi najstarszego drzewa ze wszystkich wyciętych.
Przykład:
Dla:
5 6
3 4 1 2 4
3 1 2 4 6
6 9 1 1 7
1 7 9 4 1
1 1 1 1 6
Poprawny wynik to:
2
No i wymyśliłem że można dla każdego drzewa zrobić optymalne rozwiązanie tzn dla każdego drzewa dodawać do kolejki priorytetowej jego sąsiadów których nie użyliśmy do budowy domu i brać zawsze tego optymalnego i stworzyłem taki kod
#include "bits/stdc++.h"
using namespace std;
int find_min_age(int i, int j, vector<vector<int>> las, int d){
vector<int> dirs = {0, 1, 0, -1, 1, 0, -1, 0};
vector<vector<bool>> seen(las.size(), vector<bool>(las.size()));
priority_queue<pair<int, pair<int, int>>> kolejka;
int min_age, ch_i, ch_j;
min_age = las[i][j];
seen[i][j] = true;
while (d){
for (int dir = 0; dir < 8; dir += 2){
ch_i = i + dirs[dir];
ch_j = j + dirs[dir + 1];
if (0 <= ch_i && ch_i < las.size() && 0 <= ch_j && ch_j < las.size())
if (seen[ch_i][ch_j] == false)
kolejka.push(make_pair(las[ch_i][ch_j] * -1, make_pair(ch_i, ch_j)));
}
min_age = max(min_age, kolejka.top().first * -1);
i = kolejka.top().second.first;
j = kolejka.top().second.second;
seen[i][j] = true;
kolejka.pop();
d--;
}
return min_age;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int n, d, min_age;
cin >> n >> d;
vector<vector<int>> las(n, vector<int>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> las[i][j];
min_age = 1000000000 + 1;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
min_age = min(min_age, find_min_age(i, j, las, d-1)); //d-1 bo już użyjemy drzewa o indeksach i, j
cout << min_age;
return 0;
}
niestety w jednym teście dostaję błędną odpowiedź a w kilku przekraczam czas o 0.01, pomoże mi ktoś zrozumieć gdzie robię błąd?
Tutaj testuje rozwiązania, zadanie ma nazwę "Las"