Wyszukiwanie ścieżek Roguelike

Twoim zadaniem będzie, biorąc pod uwagę dwuwymiarowy układ elementów opisanych poniżej, który reprezentuje loch, wyprowadzenie lub zwrócenie pojedynczej liczby reprezentującej ilość sztuk złota, które łotr może zebrać bez budzenia potworów.

Elementy tablicy są następujące:

1. Puste spacje są reprezentowane przez jedną .lub spację, twoje połączenie;
2. Pozycję początkową Łotra reprezentuje oczywiście @;
3. Kawałek złota jest reprezentowany przez $;
4. Ściany są reprezentowane przez #;
5. Potwory są reprezentowane przez postacie z następującym regexp: [a-zA-Z*&].

Tablica nie może zawierać żadnych znaków niewymienionych powyżej, więc możesz założyć, że wszystko, co nie jest ścianą, pustą przestrzenią, łotrem lub złotym kawałkiem, jest potworem.

Reguły wyszukiwania ścieżek są następujące:

1. Łotrzyk może przechodzić tylko przez puste komórki lub komórki zawierające złoto;
2. Przejście do sąsiedniej lub po przekątnej komórki wymaga tury;
3. Zbieranie złota jest natychmiastowe;
4. Łotrzyk nie może pozostać w sąsiedztwie potwora przez więcej niż jedną turę, nie budząc go, co jest zabronione;
5. Łotrzyk może wejść do obszaru świadomości potwora dowolną liczbę razy, potwór obudzi się tylko wtedy, gdy nieuczciwy spędzi w pobliżu dwie kolejne tury.

Reguły wejściowe i wyjściowe

Możesz uzyskać dane wejściowe w dowolnym rozsądnym formacie, w tym w tablicy dwuwymiarowej, tablicy płaskiej, ciągu lub cokolwiek innego. Jeśli to ułatwi ci życie, możesz również wziąć wymiary tablicy.

Gwarantujemy, że łotrzyk nie będzie na początku w pobliżu potwora.

Pełny program lub funkcja jest w porządku.

Punktacja

To jest golf golfowy , wynik to liczba bajtów przesłanych danych, przy czym mniej jest lepszych.

Przypadki testowe

Używam kropek do pustych miejsc tutaj w celu zapewnienia czytelności, jeśli chcesz, możesz użyć spacji (patrz wyżej). Zauważ też, że to czysty zbieg okoliczności, że łotr zawsze znajduje się w lewym górnym rogu, twój kod powinien również obsługiwać każdą inną prawidłową pozycję.

1)
@..
.$.
...  -> 1

Tylko test rozsądku.

2)
@....
...g$
.....  -> 0

Ponownie test poczytalności.

3)
@....
...$g
.....  -> 1

Łotrzyk może złapać złoto, wchodząc z lewej strony.

4)
@....g..
.......$
........
.....h..  -> 1

Łotrzyk może zygzakować między potworami, nigdy nie pozostając w pobliżu więcej niż jednej tury.

5)
@....z..
.......$
.....b..  -> 0

Taktyka z poprzedniego przypadku testowego tutaj nie działa - obszary wrażliwości potworów pokrywają się.

6)
@$#.
###$
....  -> 1

Test poczytalność.

7)
@..#..
$.$g.$
...#..  -> 2

Tak samo.

8)
@#.d#$
$...##
e.....
..$...
##..$b
.#..g$  -> 3

Ze wszystkich złotych tutaj można bezpiecznie dotrzeć tylko do trzech: złoto w pobliżu pozycji początkowej można uzyskać, przesuwając jedną w dół, a następnie z powrotem do pozycji początkowej. Aby uciec z lewego górnego rogu, łotrzyk musi dwukrotnie przejść po przekątnej w dół w prawo. Złoto w środku nie stanowi wyzwania. Zewnętrzne złoto strzeżone gi bmożna je zdobyć, poruszając się po przekątnej z miejsca na prawo od środkowego złota, a następnie z powrotem. Reszty nie można zdobyć: złoto po prawej u góry jest blokowane przez ściany, a złoto po prawej u dołu wymaga dwóch tur w obszarach wrażliwości potworów.

Następujące przypadki testowe zostały hojnie przekazane przez mbomb007.

9)
  12345678
a @....g.D
b .......$
c ......#.
d .....h..  -> 1

Ten jest trudny. Ścieżka jest b4-b5-c6-b7-c8-b8(grab).

10)
  12345678
a @....g.D
b .......$
c .......#
d .....h..  -> 1

Ścieżka jest [bc]4-c5-b6-c7-b8(grab).

11)
  12345678
a @....g.D
b ......#$
c .......#
d .....h..  -> 1

Dodatkowa ściana tak naprawdę nic nie zmienia, [bc]4-c5-b6-c7-b8(grab)wciąż jest rozwiązaniem.

poprzednie rozwiązania (część z nich) można znaleźć w kontenerze stopki w łączu tio (prawdopodobnie są one bardziej czytelne)

JavaScript (Node.js) , 883 436 411 360 345 311 bajtów

g=>g.map((r,y)=>[...r].map((c,x)=>A+=c=="$"&&P(g,x,y)),A=0)|A
P=(g,x,y,m={},p={},I=i=9,M={})=>{if(/[.$]/.test(c=(g[y]||0)[x])){for(;i--;)if(/^[^.@$#]$/.test(C=(g[y+~-(i/3)]||0)[x+i%3-1])){if(m[C])return
M[C]=1}for(;I--;)if(!p[(X=x+~-(I/3))+","+(Y=y+I%3-1)]&&P(g,X,Y,M,{...p,[x+","+y]:1}))return 1}return c=="@"}

Wypróbuj online!

Wyjaśnienie -

zamiast przejść od gracza do kasy, przeszedłem od skrzynki do @. myślę, że powinienem być szybszy, ponieważ wiem, kiedy przestać patrzeć (dotrzeć do @), a kiedy szukasz gotówki, zawsze musisz się poruszać, dopóki nie pokryjesz wszystkich miejsc (i sposobów, jak się do nich dostać). więc algo jest w ten sposób dość proste - główna funkcja g.map((r,y)=>[...r].map((c,x)=>A+=c=="$"&&P(g,x,y)),A=0)|A: znajdź gotówkę -> jeśli ją znalazłeś -> zacznij szukać gracza -> jeśli go znalazłeś -> przyrost A teraz przejdźmy do wyszukiwarki ścieżek aka P, if(/[.$]/.test(c=(g[y]||[])[x]))po prostu sprawdź, czy obecna komórka jest „specjalna” -> jeśli tak, to chcemy wrócić, jeśli jest to gracz. przypadki specjalne: @ # (potwór)

for(;i--;) if(/^[a-zA-Z*&]$/.test(C=(g[y+~-(i/3)]||0)[x+i%3-1])) -> if my neighbor is a monster {if(m[C])return false -> and it already was in the previous turn - this path is not value M[C]=1} -> if not just add it to the neighbors monsters for(;I--;) if(!p[(X=x+~-(I / 3))+","+(Y=y+I%3-1)]&&P(g,X,Y,M,{...p,[x+","+y]:1}))return true iteruj ponownie sąsiadów - jeśli mnie jeszcze nie było (p to wybrana ścieżka) kontynuuj ścieżkę (wywołanie P)