zadanie z grupowaniem pionków Opcje

[marcus753]

Witam was od tygodnia męczę z piekielnie trudnym zadaniem może ktoś z was mi trochę pomoże...

Zadanie ma taką treść

Jasiu zdenerwowany że przegrał w warcaby wziął n pionków i rzucił nimi na planszę tak że każdy pionek upadł tylko na jedno pole. Jasiu chce teraz pogrupować pionki które leżą obok siebie (czyli ustalić że pionki ułożyły się np. w 5 grup 1 grupa składa się z 3 pionków druga z 2 itd...)

2 pionki zalicza się do tej samej grupy jeśli lezą obok siebie.

mam teraz taki plik wejściowy z współrzędnymi każdego pionka
rząd/kolumna
1:1
2:2
3:3
4:4

czyli pionki ułożyły się na ukos
wynikiem takiego rozłożenia pionków powinno być 1:4 (grupa 1 , składa się z 4 pionków)

gdyby było np
1:1
1:2
2:2
5:5
5:6
wynikiem takiego rozłożenia pionków powinno być 1:3, 2:2 (grupa 1 , składa się z 3 pionków ,grupa 2 , składa się z 2 pionków)

napisałem 2 skyrpty razem z jakies 200 linijek oczywiście nie zadziałały poprawnie dochodzę do momentu w którym zaczynam pisać na nowo ale sam już nie wiem jak to wszystko zrobić ;(

bedę wdzięczny za każdą pomoc sugestie itp. (skrypt nie jest na żaden konkurs gdzie wymagana jest praca indywidualna itp) żeby nie było że wyręczam się tym forum jak chcecie moge zamieścić moje dotychczasowe skrypty ale ja sam już zaczynam się w nich gubić więc nie wiem czy wam by coś dały

POZDRAWIAM (IMG:style_emoticons/default/sciana.gif) (IMG:style_emoticons/default/sciana.gif)

pomysł miałem taki żeby porównać każdy rekord do rekordów leżących obok niego w odległości 1rzedu czyli np. dla danych
1:1
1:2
2:2
5:5
5:6

porównuje 1:1 do 1:2 jeśli leżą obok siebie do nowego pliku zapisuje 1:1:1,1:2:1 (ostatnia cyfra to grupa) następnie porównuje 1:1 do 2:2 w efekcie czego do poprzedniego pliku dopisuje 1:1:1 2:2:1
nastepnie 1:1 do 5:5 jako że 5:5 leży poza najbliższym żędem pobieram kolejną zmienną do porównania czyli 1:2 porownuje do 2:2 i tu już zaczynają się schody teraz przydało by się żeby sprawdzał czy 1:2 ma już jakąś grupe a to oznacza że najpierw musiał bym otworzyć plik aby pobrać dane i na otwartym pliku otwierać go jeszcze raz aby aktualizować nie mam pojecia jak to zrobić albo ominąć...

drugi skrypt miał ignorować takie same rekordy które występują więcej niż jeden raz i zliczać ile rekordów ma tą samą grupe

[thek]

Zdefiniuj sąsiedztwo wpierw. Sąsiad to pionek o wartości od 1 do 8 włącznie, który ma wartości współrzędnych na każdej z osi w zakresie -1,+1 do współrzędnych aktualnego.
Algorytm powinien działać łańcuchowo mniej więcej na zasadzie:
1) Weź pierwszy wolny pionek z puli wszystkich i usuń go stamtąd tworząc z niego nową grupę.
2) Wyszukaj jego sąsiadów najbliższych, dodaj do grupy i też usuń z puli wszystkich.
3) Jeśli pula pusta, możesz zakończyć algorytm.
4) Weź kolejny z tej grupy i znajdź jego sąsiadów z puli, usuń je z puli wszystkich i dodaj do grupy.
5) Powtarzaj kroki od 3) aż dojdziesz do ostatniego elementu, który już nie będzie miał sąsiadów.
6) Wróć do kroku 1)
7) Powtarzaj aż brak będzie pionków w grupie tych wolnych.

Przykład wezmę Twój:
1:1, 1:2, 2:2, 5:5, 5:6
Biorę 1:1 i tworzę grupę usuwając go z puli, mam więc:
Grupa 1 -> 1:1
Pula -> 1:2, 2:2, 5:5, 5:6

Szukam sąsiadów i znajduję 1:2, 2:2, więc dodaję do grupy i usuwam z puli, mam więc:
Grupa 1 -> 1:1, 1:2, 2:2
Pula -> 5:5, 5:6

Biorę element kolejny z grupy 1 -> 1:2 Pula ma coś więc szukam sąsiadów w puli, ale ich brak, więc biorę kolejny 2:2, sprawdza ilość w puli jeszcze coś mającej tyle że tu też brak, więc szukanie się dla grupy kończy. Jeśli coś by doszło z tych szukań to automatycznie miałbym kolejne szukanie, co chyba jest logiczne (IMG:style_emoticons/default/smile.gif)

Biorę następny element z puli i tworzę grupę 2, więc mam:
Grupa 1 -> 1:1, 1:2, 2:2
Grupa 2 -> 5:5
Pula -> 5:6
Szukam sąsiadów, znajduję 5:6, usuwam z puli i dodaję do grupy.

Grupa 1 -> 1:1, 1:2, 2:2
Grupa 2 -> 5:5, 5:6
Pula -> pusta

Pula jest pusta, czyli algorytm się kończy.

Banał... (IMG:style_emoticons/default/smile.gif)

EDIT: W sumie nawet krok 7) nie jest potrzebny, bo krok 3) tak naprawdę zawsze zakończy Ci algorytm (IMG:style_emoticons/default/winksmiley.jpg) Kwestia Twojego przemyślenia to jedynie format zapisu współrzędnych pionów. Implementacja algorytmu już mając strukturę pionów to pryszcz.

Ten post edytował thek 20.01.2010, 10:50:10