ILOCAMP 2010 zadanie Las - dziwny błąd

0

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;
}
0

No może nie za dobrze wytłumaczyłem
Główną myślą jest żeby to zadanie rozwiązać na zbiorach. Na początku Wczytuję dane i uzupełniam tablice wielkości ma [n*n] elementów i jest jednowymiarowa więc chcąc dodawać każdy element i na nowo aktualizować informacje o zbiorach, muszę ją posortować (MergeSort). Druga tablica jest dwu wymiarowa [n][n] w niej mam pola poukładane w kolejności początkowej. Następnie w każdym ostatnim dodanym elemencie do konkretnego zbioru przechowywuję informacje o ilości elementów w danym zbiorze. Z pozostałych elementów dochodzę to tego ostatnio dodanego poprzez wskaźniki. Jak rozmiar zbioru wynosi tyle co d(wielkość minimalna) albo więcej to wyświetla wielkość konkretnego drzewa i program się kończy.

#include <iostream>
using namespace std;
// struktura tablicy jednowymiarowej
struct ww
{
    int wielk; // wielkość konkretnego drzewa
    int x; // pozycja x
    int y; // pozycja y
};
// struktura tablicy dwuwymiarowej
struct pp
{
    int wielk; // wielkość zbioru
    int nr; // nr pola (zbioru)
    int *numer; // wskaźnik numeru (on wskazuje na inne wskaźniki a ostatni wskazuje na nr największego drzewa, o on na wielkość)
    bool cb; // zmienna czy dane drzewo było już rozpatrywane (czy należy do jakiegoś zbioru)
};
// funkcja Merge Sort sortująca tablicę jednowymiarową
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];// tablica jednowymiarowa
    ww *pom = new ww [n*n]; // tablica dwuwymiarowa
    pp **pole = new pp *[n];
    for (int a=0; a<n; a++)
        pole[a] = new pp [n];
    for (int a=0; a<n; a++)// oznaczanie każdego drzewa jako nie dodanego do zbioru
        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++)// wczytanie tablicy jednowymiatowej
    {
        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 (dzewa mogą być dodane tylko sąsiadujące ze sobą krawędzią)
        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; // uaktualnienie rozmiaru pola 
                pole[*pole[x-1][y].numer%n][*pole[x-1][y].numer/n].numer = pole[x][y].numer; // uaktualnienie adresu największego pola w zbiorze
            }
        }
        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) // sprawdzenie warunku zadania
        {
            cout<<wielkosci[a].wielk;
            break;
        }
    }
 
    return 0;
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1