Wyzwanie
Napisz program / funkcję, która akceptuje „obraz” i generuje labirynt obrazkowy utworzony z tego obrazu.
Wejście
Twój program powinien zaakceptować dwa argumenty:
- Ja, obraz, z którego tworzy się labirynt
- S, boolean określający, czy wyświetlić rozwiązanie labiryntu
Otrzymuję w następującej formie:
.......
.#####.
.#####.
#######
.#####.
.#####.
.......
gdzie #
są komórki, które mają zostać uwzględnione w ścieżce rozwiązania .
, a komórki to komórki, które należy wykluczyć. Możesz zamienić się z .
„s, #
” s, a nowe linie z jakiegokolwiek charakteru swojego wyboru, o ile różnią się one od siebie. Alternatywnie możesz zaakceptować rzeczywistą bitmapę obrazu wejściowego.
Wynik
Powstały labirynt powinien mieć następującą formę:
###############
# #
# ### ####### #
# #.........# #
# #.#######.# #
# #.#.......# #
###.#.#########
....#.#........
#####.#.#######
# ...#..... #
# #.#######.# #
# #.........# #
# ####### ### #
# # # #
###############
gdzie #
„ściany .
” oznaczają części ścieżki, które są częścią rozwiązania, a spacje są ścieżkami wykluczonymi z rozwiązania. Te .
mogą być zastąpione spacjami, jeśli S jest fałszem. Znaki mogą zostać zamienione na inne wybrane przez ciebie postacie lub możesz wydrukować rzeczywistą mapę bitową labiryntu z podświetlonym rozwiązaniem.
Dodatkowe Szczegóły
- Ścieżki muszą mieć szerokość jednej komórki (ścieżka nie może mieć gigantycznej puli pustej przestrzeni)
- Labirynt nie może zawierać żadnych pętli
- Labirynt musi być w pełni połączony (wszystkie komórki muszą być dostępne od wejścia / wyjścia)
- Labirynt musi być otoczony murami (chyba że jest to wejście / wyjście)
- Ścieżka rozwiązania nie może zawierać ślepych zaułków
- Musi być dokładnie 1 wejście i 1 wyjście do labiryntu
- Wejście i wyjście musi być wyrównane do krawędzi siatki i przylegać do komórki znajdującej się na ścieżce rozwiązania
- Możesz wybrać miejsce wejścia i wyjścia
- Możesz założyć, że z danego obrazu wejściowego można utworzyć prawidłową ścieżkę
(Dodano w celu wyjaśnienia) Poniższy schemat pokazuje, w jaki sposób ścieżka rozwiązania jest skorelowana z obrazem wejściowym:
Input (I): | Output: | Corresponding Cells:
| | (@'s denote #'s from I)
| |
....... | ############### | ###############
.#####. | # # | # #
.#####. | # ### ####### # | # ### ####### #
####### | # #.........# # | # #@.@.@.@.@# #
.#####. | # #.#######.# # | # #.#######.# #
.#####. | # #.#.......# # | # #@#@.@.@.@# #
....... | ###.#.######### | ###.#.#########
| ....#.#........ | .@.@#@#@.@.@.@.
| #####.#.####### | #####.#.#######
| # ...#..... # | # @.@#@.@.@ #
| # #.#######.# # | # #.#######.# #
| # #.........# # | # #@.@.@.@.@# #
| # ####### ### # | # ####### ### #
| # # # # | # # # #
| ############### | ###############
| |
Przypadki testowe
Przykład konewki z Wikipedii :
Wejście:
..................
..................
.......####.......
......##..##......
.....##....##....#
.....#......#...##
.#############.##.
##..############..
#...###########...
#...##########....
#...##########....
#...##########....
#...##########....
....##########....
....##########....
....##########....
..................
..................
Dane wyjściowe (S = fałsz):
#####################################
# # # # # # #
# ### ### ### # # ##### ### ### ### #
# # # # # # # # # # #
# ### # ##### # ########### # ### # #
# # # # # # # # #
# # # ### ##### # ### ### # ### ### #
# # # # # # # # # # # # #
# ### # ##### ##### ### ##### # # ###
# # # # # # # # #
### ####### ### ### # ### ##### ### #
# # # # # # # # # # #
# ### ##### # ### ####### # # # # # #
# # # # # # # #
# # ##### ############# ### ### ### #
# # # # # # # # # #
# ### # ####### # ### ### # # ### # #
# # # # # # # # # #
# # # ### ######### # # ##### # #####
# # # # # # # # # # # #
# ##### # # ##### # ##### # # ### # #
# # # # # # # # # # #
# ### ### ### # ### # ##### ####### #
# # # # # # # # # #
# # # # ####### # ### # ##### # ### #
# # # # # # # # # # #
### # # # # # ############# # ### # #
# # # # # # # # # # #
##### # # ##### ####### # ### ##### #
# # # # # # # # #
##### # # # # ####### # ### #########
# # # # # #
# ### ######### ############# # #####
# # # # # # # # #
# # ######### # ####### ####### ### #
# # # #
#####################################
Dane wyjściowe (S = prawda):
#####################################
# # # # # # #
# ### ### ### # # ##### ### ### ### #
# # # # # # # # # # #
# ### # ##### # ########### # ### # #
# # # #....... # # # # #
# # # ### #####.# ###.### # ### ### #
# # # # #...# # #...# # # # #
# ### # #####.##### ###.##### # # ###
# # # ...# # #... # # #..
### #######.### ### # ###.##### ###.#
# # #.# # # #.# # #...#
# ### #####.# ### #######.# # # #.# #
# #.......#.............#...# #...# #
# #.#####.#############.###.###.### #
#...# #.......#.....#...#.#...# # #
#.### # #######.#.###.###.#.#.### # #
#.# # # .......#...#.#...#...# #
#.# # ###.#########.#.#.##### # #####
#.# # #.#.......#.#...#...# # # #
#.##### #.#.#####.#.#####.#.# ### # #
#. #.#...#...#.#.....#.# # # #
#.### ###.###.#.###.#.#####.####### #
#. # # #.....#.#...#.#..... # #
#.# # # #######.#.###.#.##### # ### #
..# # # #...#...#.....#.....# # # #
### # # #.#.#.#############.# ### # #
# # # #.#...#.........#...# # # #
##### # #.#####.#######.#.### ##### #
# # #.#...#.......#.#...# #
##### # #.#.#.#######.#.###.#########
# # ...#.........#..... # #
# ### ######### ############# # #####
# # # # # # # # #
# # ######### # ####### ####### ### #
# # # #
#####################################
Przykład mapy bitowej (taki sam labirynt jak powyżej):
Dane wejściowe: Dane wyjściowe (S = fałsz): Dane wyjściowe (S = prawda):
źródło
Odpowiedzi:
Python 3, 1599 bajtów
Uważam, że jest to fajny projekt i bardzo interesujący (i nieco długi). Kiedy to zobaczyłem, przypomniałem sobie lato, które spędziłem wyłącznie na pisaniu i ulepszaniu algorytmu generowania labiryntu i od razu zacząłem nad tym pracować.
Po chwili miałem początkowy szkic o długości około 6000 bajtów i następne kilka godzin spędziłem na kondensowaniu go w następujący program:
To, co jest równie niesensowne, jak labirynt ascii-art, to ...
Warto zauważyć, że ponieważ funkcja losowa nie jest używana, dopóki nie zostanie znaleziona poprawna ścieżka, bez względu na to, ile razy podano takie same dane wejściowe, trasa od początku do końca będzie taka sama i, podczas gdy ten program robi pracując nad powyższymi przykładami, czasami nie będzie w stanie znaleźć rozwiązania, jeśli „wpędzi się w ścianę”, że tak powiem.
Podczas uruchamiania powyższych przykładów daje to:
to:
i to:
Dla każdego, kto chciałby spróbować uruchomić ten program samodzielnie, użyj polecenia
M(Image, Show solution)
. Polecam użycie potrójnych cudzysłowów do wprowadzenia obrazu, ponieważ w przeciwnym razie będzie wiele znaków odwrotnego ukośnika lub znaków nowej linii.źródło
0
zamiastpass
,l.append(a);l.append(b)
->l+=a,b
,l.append(a)
->l+=[a]
, warto przypisać'#'
do zmiennej, idef E(G,y,z):\n c=[]
->def E(G,y,z,c=[]):
if G[r][c]==1 or G[r][c]==2:
->if 0<G[r][c]<3:
,s=[0]\n for x in R(L(I[0])*2):s+=[0]
->s=[0]*(1+L(I[0])*2)
i (myślę, że jeszcze tego nie przetestowałem)G=[s]
->*G=s
.except:0
,l+=a,b
is=[0]*(1+L(I[0])*2)
naprawdę pomogło. Niestety, z jakiegokolwiek powodu przypisanie c w wywołaniu funkcji nie resetuje go przez wiele wywołań, co oznaczało, że przestał działać, G [r] [c] może być ciągiem, więc nie mogę użyć <lub> na nim i * G = s dał mi błąd składniowy. Mimo to świetna rada.G[r][c]
może być łańcuchem,G[r][c]in[1,2]
powinno działać.