Autor Wątek: Gra w kropki - otoczka  (Przeczytany 1405 razy)

Offline .Dexter.

  • Użytkownik

# Maj 28, 2013, 20:56:20
Cześć, myślałem ostatnio o prostej grze jaką jest Gra w Kropki. Problemem jest tu szukanie otoczki, która nie musi być wypukła. Nie mogę wymyślić nic sensownego. Do głowy przychodzi mi jedynie rozwiązanie polegające na tym, że przy stawianiu każdej kropki sprawdzane są ścieżki w każdą stronę (czyli 8 stron dla każdego ruchu). I jeśli ścieżka wróci do punktu rozpoczęcia to mamy otoczkę... Jednak to trochę naiwne podejście. Do tego dochodzi sprawdzanie czy na drodze nie stoi już inna linia itd.

Ma ktoś jakiś pomysł? :)

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Avaj

  • Użytkownik

# Maj 28, 2013, 20:59:00
Hmm, a jakby tak potraktować to jako graf i szukać najdłuższych cykli w grafie?

Offline koirat

  • Użytkownik

# Maj 28, 2013, 21:10:09
A może szukaj dla danego punktu czy ma otoczkę. Można to zrobić za pomocą algorytmu flood-fill.

Offline Kos

  • Użytkownik
    • kos.gd

# Czerwiec 03, 2013, 22:16:07
A może szukaj dla danego punktu czy ma otoczkę. Można to zrobić za pomocą algorytmu flood-fill.
+1. Po postawieniu kropki zapuszczasz floodfilla po kolei na wszystkich sąsiadach, na których nie ma kropki tego samego koloru. Jeżeli floodfill się się skończy (zatrzyma zanim dotknie krawędzi planszy), to otrzymujesz pewien obszar możliwy do otoczenia. Od razu dowiesz się, czy są w nim jakieś kropki innych kolorów.

Wydaje mi się, że wynikiem takiego podejścia będzie najmniejszy możliwy obszar; można potem się jeszcze przejechać parę razy po krawędziach i go "rozdmuchać".