[inf, algorytm] Zliczanie grupek danej wartości w tablicy 2d

	B O A R D
	» Board » Zadaj pytanie » Archiwum » Szukaj » Stylizacja

M E N U

» Nowości

» Archiwum

» Recenzje / Testy

» Board

» Rejestracja

Szukaj @ TwojePC

	OBECNI NA TPC
	» Demo 10:57 » zibi13 10:56 » MARtiuS 10:54 » DYD 10:54 » Dexter 10:53 » Remek 10:49 » Qjanusz 10:47 » jenot 10:41 » Mariosti 10:40 » power 10:37 » nth4 10:37 » JE Jacaw 10:36 » biEski 10:31 » MARC 10:24 » selves 10:19 » NimnuL 10:18 » adolphik 10:16 » Wedrowiec 10:15 » bagi_glog 10:14 » Kenny 10:14 Dzisiaj przeczytano 12286 postów, wczoraj 33478 Szybkie ładowanie jest: włączone.

ccc

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 fill
dzisiaj 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?
:)
1. ... , 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 ...
  1. 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 ...