Napisz program lub funkcję, która przyjmuje trzy liczby całkowite, szerokość w, wysokość hi liczbę kroków s. Będziesz rysowanie non-self-przecinających błądzenia losowego s kroki długo na zasadzie 5*wprzez 5*hpiksela obrazu, w którym każda komórka 5 przez 5 piksel jest albo pusty (czysty beż) lub jednej z tych dwanaście prostych „rury”:

Obraz powyżej jest powiększony, aby pokazać szczegóły. Oto rury w rzeczywistym rozmiarze:

^{(Szare linie służą tylko do oddzielenia typów rur).}

Spacer losowy będzie pojedynczą ciągłą ścieżką rury, która zaczyna się w jednym punkcie końcowym rury (jeden z czterech dolnych typów rur) i kończy w innym punkcie końcowym rury.

Start z pustym wprzez hsiatkę i losowo wybrać jedną komórkę być punktem wyjścia. Następnie losowo wybierz jeden z czterech kierunków, od którego chcesz zacząć, i narysuj odpowiedni punkt końcowy rury. Ta komórka początkowa oznacza pierwszy krok na spacerze i za każdym razem, gdy narysujesz nową komórkę lub zastąpisz istniejącą, liczy się to jako kolejny krok.

Teraz, wielokrotnie, losowo wybierz iść w prawo, w lewo lub prosto, rysując odpowiednią komórkę rury, jeśli wybrany kierunek jest prawidłowy. Wróć i wybierz ponownie, jeśli kierunek jest nieprawidłowy, dopóki nie zostanie utworzona pełna sścieżka kroku. Ścieżka powinna kończyć się punktem końcowym potoku, który może znajdować się w dowolnym miejscu na siatce, w zależności od kursu pokonanego przez ścieżkę.

Bardzo ważne jest, aby pamiętać, że tylko dwie proste komórki rurowe mogą zostać zastąpione i tylko przez prostą komórkę rurową o przeciwnej orientacji, czego wynikiem jest komórka przecięcia. W przeciwnym razie wszystkie rury muszą być umieszczone w pustych komórkach.

Po narysowaniu skrzyżowania należy narysować część ścieżki dalej od komórki początkowej.

Od Ciebie zależy, czy siatka ma okresowe warunki brzegowe (PBC), tj. Czy rura wychodząca z jednej strony siatki wyjdzie na drugą stronę. Bez PBC granica siatki liczy się jako bariera, na którą można wpaść tak jak inne rury.

Przypadki specjalne

• Gdy swynosi 0, nie należy rysować żadnych rur, a wynik powinien być pusty 5*wwedług 5*hobrazu (tzn. Wszystkie beżowe).

• Kiedy s1 oznacza pojedynczą końcówkę rury

  (Rzeczywista wielkość: )

  należy narysować w losowo wybranej komórce początkowej.

Inne szczegóły

• Możesz założyć, że sjest to co najwyżej, w*hwięc ścieżka zawsze będzie możliwa. (Chociaż dłuższe ścieżki są możliwe ze względu na skrzyżowania.)
• wi hzawsze będą pozytywne.
• Wszystkie losowe wybory muszą być jednakowo losowe. np. nie powinieneś unikać wykonywania skrzyżowań, gdy są one możliwe, nawet jeśli to ułatwia problem. Generatory liczb pseudolosowych są dozwolone.
• Zamiast czarnego, niebieskiego i beżowego można zastosować dowolne trzy odrębne wizualnie kolory.
• Twoje zdjęcia wyjściowe mogą być powiększone, tak aby były naprawdę 5*w*kw 5*h*kpikselach, gdzie kjest dodatnią liczbą całkowitą. (Zalecane jest powiększenie wszystkich opublikowanych przykładów, nawet jeśli masz k1.)
• Można użyć dowolnego popularnego bezstratnego formatu pliku obrazu, a obraz może zostać zapisany w pliku, wyświetlony lub wyrzucony na surowo na standardowe wyjście.

Najkrótszy kod w bajtach wygrywa.

Przykłady

^{(Wszystko powiększone o 500%.)}

Jeśli wejście jest, w=2, h=1, s=0wówczas wyjście zawsze będzie:

Jeśli wejście jest, w=2, h=1, s=1wówczas wyjście będzie jednym z tych obrazów z jednakową szansą:

Jeśli wejście jest, w=2, h=1, s=2wtedy wyjście będzie

lub ewentualnie

jeżeli zakłada się, że siatka ma PBC.

(Pamiętaj, że rozpoczęcie ścieżki w podobny sposób uniemożliwiłoby drugi krok).

Oto kilka możliwych wyników w=3, h=2, s=6, przy założeniu PBC:

Oto możliwe wyjście w=3, h=3, s=9, przy założeniu PBC:

Zauważ, że ścieżka nie musiała obejmować wszystkich komórek z powodu przecięcia liczonego jako dwa kroki. Możemy również wywnioskować, że narożny punkt końcowy był komórką początkową, ponieważ wiadukt przecięcia musiał zostać narysowany później. W ten sposób możemy wywnioskować sekwencję losowych wyborów, które zostały dokonane:

start at top left, facing east
go straight
go right
go right
go right
go straight
go left
go right
end

Na koniec oto przykłady w=4, h=5, s=20i w=4, h=5, s=16:

CJam, 274

q~:K;:B;:A;{0aA*aB*:M5*5f*:I;K{[Bmr:QAmr:P]5f*:R;3Ym*{R.+:)2{1$0=I=2$W=@tI@0=@t:I;}:F~}/R2f+1FK({MQ=P=:EY4mr:D#&1{{MQMQ=PE2D#+tt:M;}:G~7,1>[W0_1_0_W]2/D=:Off*{[QP]5f*2f+.+_:H1F_OW%.+2FOW%.m2F}/H2FO~P+:P;Q+:Q;MQ=P=:E_5YD2%-*=!JK2-=+*1{D2+4%:D;G}?}?}fJ]}0?}g'P2NA5*SI,N2NI:+N*

Wypróbuj online

Wykorzystuje PBC, wyjścia w formacie PGM. Możesz usunąć :+koniec, aby uzyskać ładniejszy efekt wizualny w przeglądarce.

Przy większych nakładach jest bardzo wolny, szczególnie jeśli liczba kroków jest zbliżona do obszaru.

Przykład wyniku dla danych wejściowych 4 3 10(skalowane 500%):

Krótkie wyjaśnienie:

Ogólne podejście to:

• powtarzaj wszystkie poniższe kroki, aż się powiedzie:
• zainicjuj 2 macierze: jedno nagranie, które strony są używane w każdej komórce, i jedno dla obrazu
• jeśli s = 0, to koniec, w przeciwnym razie:
• wybierz losową komórkę i narysuj kwadrat, a następnie wykonaj następujące s-1 razy:
• wybierz losowy kierunek; jeśli ta strona jest już użyta, zakończ działanie i zacznij od nowa
• zaznacz bok jako używany i narysuj rzeczywistą rurę na obrazie (narysuj 3 sąsiednie linie o długości 6, zaczynając tuż „po” środkowym pikselu bieżącej komórki, a następnie dodając kropkę, aby zakryć koniec rury)
• zaktualizuj bieżącą pozycję (przejście do następnej komórki)
• sprawdź, czy komórka jest pusta lub czy jest to prawidłowe przejście; jeśli nie, zawiedź i zacznij od nowa
• zaznacz bok w przeciwnym kierunku, jak w tej komórce, a następnie kontynuuj pętlę

QBasic, 517 516 bajtów

RANDOMIZE TIMER
SCREEN 9
INPUT w,h,s
1CLS
IF s=0GOTO 9
x=5*INT(RND*w)
y=5*INT(RND*h)
GOSUB 7
FOR k=1TO s-1
r=INT(RND*4)+1
a=x+5*((r=2)-(r=4))
b=y+5*((r=1)-(r=3))
c=(POINT(a,b+2)*POINT(a+4,b+2)+POINT(a+2,b)*POINT(a+2,b+4))*(0=POINT((a+x)\2+2,(b+y)\2+2))
IF((0=POINT(a+2,b+2))+c)*(a>=0)*(b>=0)*(a<5*w)*(b<5*h)=0GOTO 1
x=a
y=b
GOSUB 7
o=1AND r
p=x-2+3*o-5*(r=2)
q=y+1-3*o-5*(r=1)
u=p+3-o
v=q+2+o
LINE(p,q)-(u,v),7,B
LINE(p+o,q+1-o)-(u-o,v-1+o),1
NEXT
9IF c GOTO 1
END
7LINE(x+1,y+1)-(x+3,y+3),7,B
PSET(x+2,y+2),1
RETURN

• Pobiera w, hi sod danych wejściowych użytkownika, oddzielonych przecinkami.
• Dane wyjściowe są rysowane na ekranie. Podczas gdy program szuka rozwiązania, możesz zobaczyć migające częściowe rozwiązania.
• Nie stosuje okresowych warunków brzegowych. Łatwiej było mi rysować i testować połączenia rur bez martwienia się, że połowa rury będzie po jednej stronie kratki, a połowa po drugiej.

Podejście polega na wypróbowaniu losowego kierunku na każdym kroku i rozpoczęciu od początku, jeśli spowoduje to nieprawidłowy ruch. Rysujemy rury zgodnie z ustalonymi kierunkami i używamy POINTdo testowania punktów na ekranie pod kątem naszych warunków ważności. Ruch jest ważny, jeśli nie wykracza poza granice siatki i:

1. Przeniesiona do komórki jest pusta; lub
2. Obie
   1. Przeniesiona do komórki zawiera rurkę przechodzącą przez nią poziomo lub pionowo oraz
   2. Nowy odcinek rury nie podwaja istniejącego odcinka rury

Podobnie jak odpowiedź CJam aditsu , ten kod jest bardzo wolny i może być przytłaczająco powolny, jeśli sstanowi znaczną część w*h. W mojej konfiguracji QB64 pojawia się odpowiedź 5,5,19dość szybko, ale trwa to dłużej niż byłem gotów czekać 5,5,20.

Jeśli chcesz uruchamiać większe / bardziej gęsto upakowane przykłady, oto moje oryginalne podejście z użyciem wyszukiwania w pierwszej kolejności . Jest znacznie wydajniejszy, kosztem aż 300 dodatkowych bajtów.

RANDOMIZE TIMER
SCREEN 9
INPUT w,h,s
DIM t(s),m(s)
0
FOR z=1TO s
t(z)=-1
NEXT
i=5*INT(RND*w)
j=5*INT(RND*h)
k=1
1CLS
IF s=0GOTO 9
x=i
y=j
GOSUB 7
FOR z=1TO k-1
r=m(z)
GOSUB 6
x=a
y=b
GOSUB 7
o=1AND r
p=x-2+3*o-5*(r=2)
q=y+1-3*o-5*(r=1)
u=p+3-o
v=q+2+o
LINE(p,q)-(u,v),7,B
LINE(p+o,q+1-o)-(u-o,v-1+o),1
NEXT
IF c*(k=s)THEN k=k-1:GOTO 1 ELSE IF k=s GOTO 9
IF k<1GOTO 0
IF t(k)>=0GOTO 4
t(k)=0
f=30
WHILE f
r=INT(RND*4)+1
IF f AND 2^r THEN t(k)=t(k)*5+r:f=f-2^r
WEND
4r=t(k)MOD 5
m(k)=r
t(k)=t(k)\5
GOSUB 6
c=(POINT(a,b+2)*POINT(a+4,b+2)+POINT(a+2,b)*POINT(a+2,b+4))*(0=POINT((a+x)\2+2,(b+y)\2+2))
IF((0=POINT(a+2,b+2))+c)*(a>=0)*(b>=0)*(a<5*w)*(b<5*h)THEN k=k+1 ELSE IF t(k)>0GOTO 4 ELSE t(k)=-1:k=k-1
GOTO 1
6a=x+5*((r=2)-(r=4))
b=y+5*((r=1)-(r=3))
RETURN
7LINE(x+1,y+1)-(x+3,y+3),7,B
PSET(x+2,y+2),1
RETURN
9

Przykładowe dane wyjściowe dla danych wejściowych 10, 10, 100, rzeczywisty rozmiar:

Jeszcze bardziej udoskonaloną wersję można znaleźć w tej treści . Oprócz tego, że nie jest golfistą i nie jest dokładnie komentowany, skaluje on wynik o stały współczynnik i pozwala na ustawienie opóźnienia między krokami, umożliwiając obserwowanie algorytmu DFS w działaniu. Oto przykładowy przebieg: