|
TwojePC.pl © 2001 - 2024
|
 |
A R C H I W A L N A W I A D O M O Ś Ć |
 |
| |
|
[inf, algorytm] Zliczanie grupek danej wartości w tablicy 2d , rzymo 10/03/16 10:47
Zaryzykuję i zapytam :) bo myślę, myślę i na razie nie wiem jak podejść do problemu...
Jest sobie tablica 2D, np. 6x6, albo 350x200 - rozmiary w miarę dowolne.
Różne operacje, na końcu pojawia się w pewnych miejscach wartość 1. Mam zliczyć grupki tych jedynek (tylko 1, reszta wartości nieważna) i wybrać najliczniejszą grupkę.
Jest dodatkowy warunek - jeśli jedynka jest oddzielona jednym znaczkiem od innych, to cały czas liczy się to jako jedną grupę.
Daru tłumaczenia nie mam, obrazek powinien wyjaśnić o co chodzi ;) http://abload.de/img/rysdfp1t.jpg - tu najbardziej liczna grupa to 4 sztuki jedynek (nie jest ważne, że takich grup jest kilka).... ITX ... - hmm , bartek_mi 10/03/16 10:52
rekurencja w stylu flood filldzisiaj jest jutrzejszym wczoraj - Najpierw bym przelecial po tej tabelce w obu kierunkach i jesli poprzednik i następnik , ptoki 10/03/16 11:41
równy jeden to wstawial bym tam zero.
A potem tak jak bartek_mi sugeruje, jechać "flood fillem" rekurencyjnie i zliczać kazda grupke osobno.
W drugiej identycznej tablicy zaznaczac sobie gdzie już byłem i tych pól już nie analizować.
Czyli:
1. kasujemy do zera te rodzynki miedzy jedynkami
2. robimy identyczna tabelke w której zaznaczamy ze dane pole jest juz zliczone.
3. Lecimy po kolejnych polach z tablicy 2. które nie są zaznaczone jako odwiedzone i dla nich inicjujemy punkt 4.
4. Lecimy po sąsiadujących polach w tablicy 1. dla pól równych 1 lub zero zliczamy je. sumujemy te jedynki, zaznaczamy odwiedzone pola w tablicy 2. po skonczeniu sie rekurencji zapisujemy wynik do listy wyników. wracamy do punktu 3.
5. Liste wyników sortujemy. i wyswietlamy max.
Dla elegancji warto zapisac koordynaty dowolnego punktu z tej grupy którą zliczamy.
Co wygrałem?
:)
- ... , rzymo 10/03/16 12:22
czyli tak:
1) grupki jedynek oddzielone jednym polem łączę za pomocą jakiegoś wybranego znaczka, np. 0
2) wtedy flood fill (podejrzewam że na liście/kolejce, bo stos przepełnię) i dostaję oddzielone od siebie "pola jedynek", uwzględnione w tym jest już jedno pole/komórka przerwy między jedynkami
3) potem zliczenie, wyznaczenie max i tyle
wydaje się proste :) teraz tylko trochę pisania - przełożenie na kod...
... ITX ... - Zliczasz w chwili przechodzenia po polu. , ptoki 10/03/16 12:33
http://stackoverflow.com/...f-flood-fill-algorithm
Nawet jak robisz nierekurencyjnie tylko w kolejce/liscie to i tak musisz sobie zaznaczać gdzie już byles aby nie zliczyc tego samego pola wiecej niz raz.
- ... , rzymo 13/03/16 20:58
dla potomnych - wystarczyło delikatnie zmodyfikować otoczenie sąsiadów (uwzględnienie przeskoku o jedno pole) i ładnie da się zrobić na grafach. Przeszukiwanie w głąb / wszerz (w zależności od preferencji) i już - działa i to całkiem szybko...... ITX ...
|
|
|
|
 |
All rights reserved ® Copyright and Design 2001-2024, TwojePC.PL |
 |
|
|
|
