Biorąc pod uwagę czarno-biały obraz z białym tłem i zestawem czarnych kropek, pomaluj zestaw białych pikseli na czerwono, tak aby między każdą parą czarnych pikseli była ścieżka.
Detale
Ścieżka to zestaw połączonych pikseli (łączność w 8 dzielnicach). Czarne piksele mogą być użyte jako część ścieżek. Celem jest zminimalizowanie zestawu czerwonych pikseli w powyższych warunkach i uzyskanie odpowiedniego obrazu.
Nie musisz szukać optymalnego rozwiązania.
Trywialnym i jednocześnie najgorszym rozwiązaniem jest po prostu pomalowanie wszystkich białych pikseli na czerwono.
Przykład (w celu zwiększenia widoczności piksele):
Detale
- Podany obraz pikselowy (w dowolnym odpowiednim formacie) zwraca inny obraz z połączonymi kropkami, jak określono powyżej, a także liczbę całkowitą wskazującą, ile użyto czerwonego piksela.
- Wynik jest iloczynem (1 + liczba czerwonych pikseli) dla każdej z 14 przypadków testowych.
- Bramka ma najniższy wynik.
Przypadki testowe
14 przypadków testowych pokazano poniżej. Program pythonowy do weryfikacji połączenia wyjść można znaleźć tutaj.
Meta
Dzięki @Veskah, @Fatalize, @ wizzwizz4 i @trichoplax za różne sugestie.
Odpowiedzi:
C, wynik 2,397x10 ^ 38
Człowieku, zajęło to zbyt wiele czasu, najprawdopodobniej z powodu mojego wyboru języka. Algorytm działał dość wcześnie, ale napotkałem wiele problemów z alokacją pamięci (nie mogłem rekurencyjnie zwolnić rzeczy z powodu przepełnienia stosu, rozmiary przecieków były ogromne).
Nadal! To bije drugi wpis w każdym przypadku testowym, a
może nawet optymalnezbliża się do siebie lub dokładnie optymalne rozwiązania przez większość czasu.W każdym razie oto kod:
Testowane na: Arch Linux, GCC 9.1.0,
-O3
Ten kod pobiera dane wejściowe / wyjściowe w niestandardowym pliku, który nazywam „cppm” (ponieważ jest jak skrócona wersja klasycznego formatu PPM). Skrypt Pythona do konwersji do / z niego znajduje się poniżej:
Wyjaśnienie algorytmu
Działanie tego algorytmu polega na tym, że zaczyna się od znalezienia wszystkich połączonych kształtów na obrazie, w tym czerwonych pikseli. Następnie bierze pierwszy i rozszerza swoją granicę o jeden piksel na raz, aż napotka inny kształt. Następnie koloruje wszystkie piksele od dotyku do pierwotnego kształtu (używając listy połączonej, którą utworzył po drodze, aby śledzić). Na koniec powtarza ten proces, znajdując wszystkie utworzone nowe kształty, dopóki nie zostanie tylko jeden kształt.
Galeria obrazów
Testcase 1, 183 pikseliTestcase 2, 140 pikseli
Testcase 3, 244 pikseli
Testcase 4, 42 pikseli
Testcase 5, 622 pikseli
Testcase 6, 1 piksel
Testcase 7, 104 pikseli
Testcase 8, 2286 pikseli
Testcase 9, 22 piksele
Testcase 10, 31581 pikseli
Testcase 11, 21421 pikseli
Testcase 12, 5465 pikseli
Testcase 13, 4679 pikseli
Testcase 14, 7362 pikseli
źródło
Python, 2,62 * 10 ^ 40
Algorytm ten po prostu wypełnia (BFS) płaszczyznę, zaczynając od czarnych części obrazu, gdzie dla każdego nowego piksela rejestrujemy, z której czarnej części został zalany. Gdy tylko mamy dwa sąsiednie piksele z różnymi czarnymi częściami jako przodkami, zasadniczo łączymy te dwie czarne części, łącząc je przez przodków dwóch sąsiadów, których właśnie znaleźliśmy. Teoretycznie można to zaimplementować w
O(#pixels)
, ale aby utrzymać ilość kodu na akceptowalnym poziomie, implementacja ta jest nieco gorsza.Wynik
Wynik
źródło
Python 3:
1,7x10 ^ 421,5x10 ^ 41Korzystanie
Pillow
,numpy
iscipy
.Przyjmuje się, że obrazy znajdują się w
images
folderze znajdującym się w tym samym katalogu co skrypt.Oświadczenie : Przetwarzanie wszystkich zdjęć zajmuje dużo czasu.
Kod
Wyjaśnienie
Trywialne rozwiązanie. Zaczynamy od zmiany koloru wszystkich białych pikseli obrazu na czerwony. W ten sposób gwarantuje się, że wszystkie elementy (dowolna wyspa czarnych pikseli) są połączone.
Następnie iterujemy wszystkie piksele na obrazie, zaczynając od lewego górnego rogu i przesuwając się w prawo i w dół. Za każdy znaleziony czerwony piksel zmieniamy jego kolor na biały. Jeśli po tej zmianie koloru nadal jest tylko jeden element (element jest teraz dowolną wyspą czarnych i czerwonych pikseli), pozostawiamy piksel biały i przechodzimy do następnego piksela. Jeśli jednak po zmianie koloru z czerwonego na biały liczba elementów jest większa niż jeden, piksel pozostawiamy na czerwono i przechodzimy do następnego piksela.
Aktualizacja
Jak można zobaczyć (i oczekiwać), połączenia uzyskane tylko przy użyciu tej metody wykazują regularny wzór, aw niektórych przypadkach, na przykład na 6. i 11. obrazie, występują niepotrzebne czerwone piksele.
Te dodatkowe czerwone piksele można łatwo usunąć, powtarzając ponownie obraz i wykonując te same operacje, co wyjaśniono powyżej, ale od prawego dolnego rogu do lewego górnego rogu. Ten drugi przebieg jest znacznie szybszy, ponieważ ilość czerwonych pikseli, które należy sprawdzić.
Wyniki
Obrazy, które są modyfikowane po drugim przejściu, są wyświetlane dwukrotnie, aby pokazać różnice.
Liczba czerwonych pikseli: 18825
Liczba czerwonych pikseli: 334
Liczba czerwonych pikseli: 1352
Liczba czerwonych pikseli: 20214
Liczba czerwonych pikseli: 47268
Liczba czerwonych pikseli:
6327Liczba czerwonych pikseli: 17889
Liczba czerwonych pikseli: 259
Liczba czerwonych pikseli: 6746
Liczba czerwonych pikseli: 586
Liczba czerwonych pikseli:
91Liczba czerwonych pikseli: 126
Liczba czerwonych pikseli: 212
Liczba czerwonych pikseli: 683
Obliczanie wyniku:
(1 + 6746) * (1 + 126) * (1 + 259) * (1 + 17889) * (1 + 334) * (1 + 586) * (1 + 18825) * (1 + 9) * (1 +683) * (1 + 1352) * (1 + 20214) * (1 + 212) * (1 + 63) * (1 + 47268) = 1778700054505858720992088713763655500800000 ~ 1,7x10 ^ 42
Zaktualizowano obliczenie wyniku po dodaniu drugiego podania:
(1+ 18825) * (1+ 1352) * (1+ 20214) * (1+ 47268) * (1+ 27) * (1+ 17889) * (1+ 6746) * (1+ 586) * (1 + 1) * (1+ 126) * (1+ 212) * (1+ 334) * (1 + 259) * (1 + 683) = 155636254769262638086807762454319856320000 ~ 1,5x10 ^ 41
źródło