Witam,
Ostatnio zacząłem uczyć się algorytmiki i w jednym z zadań napotkałem problem którego nie umiem sam rozwiązać.
Otóż w zadaniu http://main.edu.pl/pl/archive/ilocamp/2010/las napisałem program który wykorzystuje dwie tablice - jednowymiarową i dwuwymiarową. W tej pierwszej przechowywuję informacje o wielkości drzewa i jego pozycji. W drugiej natomiast informacje o zbiorze do którego należy konkretne drzewo. Informacje o wielkości zbioru drzew są zawsze w największym dotychczas drzewie. Pozostałe drzewa dochodzą do tego największego w zbiorze poprzez wskaźniki. Problem jest w tym, że mój program rozwiązuje tylko 4/14 przykładów.
Wiem, że to pewnie trudne zadanie ale bardzo proszę o pomoc.
#include <iostream>
using namespace std;
struct ww
{
int wielk;
int x;
int y;
};
struct pp
{
int wielk;
int nr;
int *numer;
bool cb;
};
void MergeSort(int p, int q, ww *A, ww *B)
{
if (p==q)
return;
int s = (p + q) / 2;
MergeSort(p, s, A, B);
MergeSort(s+1, q, A, B);
int i = p;
int j = s+1;
for (int k = p; k <= q; k++)
if (j>q || ( i<=s && A[i].wielk < A[j].wielk ) )
{
B[k] = A[i];
i++;
} else
{
B[k] = A[j];
j++;
}
for(int k = p ; k <= q; k++)
A[k] = B[k];
}
int main()
{
//Wczytanie danych
int d, n;
cin >> n >> d;
ww *wielkosci = new ww [n*n];
ww *pom = new ww [n*n];
pp **pole = new pp *[n];
for (int a=0; a<n; a++)
pole[a] = new pp [n];
for (int a=0; a<n; a++)
for (int b=0; b<n; b++)
pole[a][b].cb=false;
int x=0, y=0;
for (int a=0; a<n*n; a++)
{
cin >> wielkosci[a].wielk;
wielkosci[a].x=x;
wielkosci[a].y=y;
x++;
if (x==n)
{
x=0;
y++;
}
}
MergeSort(0, n*n-1, wielkosci, pom);
delete pom;
// Wyszukiwanie i poszerzanie zbiorow
for (int a=0; a<n*n; a++)
{
// Zadelkarowanie wartosci poczatkowych w danym polu
x=wielkosci[a].x;
y=wielkosci[a].y;
pole[x][y].cb=true;
pole[x][y].wielk=1;
pole[x][y].nr=y*n+x;
pole[x][y].numer =& pole[x][y].nr;
//Sprawdzanie kolejnych sytuacji
if (x!=0)
{
if (pole[x-1][y].cb==true && *pole[x-1][y].numer!=*pole[x][y].numer)
{
pole[x][y].wielk+=pole[*pole[x-1][y].numer%n][*pole[x-1][y].numer/n].wielk;
pole[*pole[x-1][y].numer%n][*pole[x-1][y].numer/n].numer = pole[x][y].numer;
}
}
if (x!=n-1)
{
if (pole[x+1][y].cb==true && *pole[x+1][y].numer!=*pole[x][y].numer)
{
pole[x][y].wielk+=pole[*pole[x+1][y].numer%n][*pole[x+1][y].numer/n].wielk;
pole[*pole[x+1][y].numer%n][*pole[x+1][y].numer/n].numer = pole[x][y].numer;
}
}
if (y!=0)
{
if (pole[x][y-1].cb==true && *pole[x][y-1].numer!=*pole[x][y].numer)
{
pole[x][y].wielk+=pole[*pole[x][y-1].numer%n][*pole[x][y-1].numer/n].wielk;
pole[*pole[x][y-1].numer%n][*pole[x][y-1].numer/n].numer = pole[x][y].numer;
}
}
if (y!=n-1)
{
if (pole[x][y+1].cb==true && *pole[x][y+1].numer!=*pole[x][y].numer)
{
pole[x][y].wielk+=pole[*pole[x][y+1].numer%n][*pole[x][y+1].numer/n].wielk;
pole[*pole[x][y+1].numer%n][*pole[x][y+1].numer/n].numer = pole[x][y].numer;
}
}
if (d<=pole[x][y].wielk)
{
cout<<wielkosci[a].wielk;
break;
}
}
return 0;
}