Wyzwanie

Biorąc pod uwagę rozmiar siatki, pozycje przeszkód, pozycję gracza i pozycję docelową, Twoim zadaniem jest znaleźć ścieżkę, aby gracz mógł dotrzeć do celu i jednocześnie unikać przeszkód (jeśli to konieczne).

Wejście

• N : Rozmiar siatkiN x N
• P : Pozycja gracza[playerposx, playerposy]
• T : Pozycja celu[targetposx, targetposy]
• O : Pozycje przeszkód[[x1, y1], [x2, y2],...,[xn, yn]]

Wynik

Ścieżka : Gracz ścieżki może dotrzeć do celu[[x1, y1], [x2, y2],...,[xn, yn]]

Zasady

1. Punkt [0,0]znajduje się w lewym górnym rogu siatki.
2. Pozycja gracza zawsze będzie po lewej stronie siatki.
3. Pozycja celu zawsze będzie po prawej stronie siatki.
4. Siatka zawsze będzie miała co najmniej jedną przeszkodę.
5. Możesz założyć, że żadna przeszkoda nie pokrywa się z pozycją gracza lub celu.
6. Nie musisz koniecznie znaleźć minimalnej ścieżki.
7. Gracz może poruszać się tylko w lewo, w prawo, w górę i w dół, a nie po przekątnej.
8. Możesz pobrać dane wejściowe w dowolny wygodny sposób.
9. Możesz założyć, że ścieżka do gracza zawsze będzie istniała.
10. Oczywiście dla każdego wejścia istnieje wiele prawidłowych ścieżek, wybierz jedną.
11. Załóżmy N > 2, że siatka będzie co najmniej 3 x 3.

Przykłady

Wejście: 9, [6, 0], [3, 8], [[0, 5], [2, 2], [6, 4], [8, 2], [8, 7]]
Możliwość wyjścia:[[6, 0], [6, 1], [6, 2], [6, 3], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [5, 8], [4, 8], [3, 8]]

Wejście: 6, [1, 0], [3, 5], [[1, 2], [2, 5], [5, 1]]
Możliwość wyjścia:[[1, 0], [1, 1], [2, 1], [2, 2], [2, 3], [2, 4], [3, 4], [3, 5]]

Uwaga

Zauważ, że dotyczy Xto wierszy i Ykols. Nie myl ich ze współrzędnymi na obrazie.

Edytować

Jak wskazano @digEmAll, ze względu na zasady #2oraz #3, playerY = 0i targetY = N-1. Tak więc, jeśli chcesz, możesz wziąć tylko jako dane wejściowe playerXi targetX(jeśli to skraca kod).

JavaScript (ES6), 135 bajtów

Pobiera dane wejściowe jako (width, [target_x, target_y], obstacles)(source_x, source_y), gdzie przeszkodą jest tablica ciągów w "X,Y"formacie.

Zwraca tablicę ciągów w "X,Y"formacie.

(n,t,o)=>g=(x,y,p=[],P=[...p,v=x+','+y])=>v==t?P:~x&~y&&x<n&y<n&[...o,...p].indexOf(v)<0&&[0,-1,0,1].some((d,i)=>r=g(x+d,y-~-i%2,P))&&r

Wypróbuj online!

Skomentował

(n, t, o) =>              // n = width of maze, t[] = target coordinates, o[] = obstacles
  g = (                   // g() = recursive search function taking:
    x, y,                 //   (x, y) = current coordinates of the player
    p = [],               //   p[] = path (a list of visited coordinates, initially empty)
    P = [                 //   P[] = new path made of:
      ...p,               //     all previous entries in p
      v = x + ',' + y     //     the current coordinates coerced to a string v = "x,y"
    ]                     //
  ) =>                    //
    v == t ?              // if v is equal to the target coordinates:
      P                   //   stop recursion and return P
    :                     // else:
      ~x & ~y             //   if neither x nor y is equal to -1
      && x < n & y < n    //   and both x and y are less than n
      & [...o, ...p]      //   and neither the list of obstacles nor the path
        .indexOf(v) < 0   //   contains a position equal to the current one:
      && [0, -1, 0, 1]    //     iterate on all 4 possible directions
        .some((d, i) =>   //     for each of them:
          r = g(          //       do a recursive call with:
            x + d,        //         the updated x
            y - ~-i % 2,  //         the updated y
            P             //         the new path
          )               //       end of recursive call
        ) && r            //     if a solution was found, return it

R 227 bajtów

function(N,P,G,O){M=diag(N+2)*0
M[O+2]=1
b=c(1,N+2)
M[row(M)%in%b|col(M)%in%b]=1
H=function(V,L){if(all(V==G+2))stop(cat(L))
M[t(V)]=2
M<<-M
for(i in 0:3){C=V+(-1)^(i%/%2)*(0:1+i)%%2
if(!M[t(C)])H(C,c(L,C-2))}}
try(H(P+2,P),T)}

Wypróbuj online!

Niezbyt krótkie i zdecydowanie nie podające najkrótszej ścieżki (np. Sprawdź pierwszy przykład).
Zasadniczo wykonuje rekurencyjne wyszukiwanie od głębokości i zatrzymuje się, gdy tylko cel zostanie osiągnięty, drukując ścieżkę.

Podziękowania dla JayCe za ulepszenie formatowania wyjściowego

Python 2 , 151 149 bajtów

N,s,e,o=input()
P=[[s]]
for p in P:x,y=k=p[-1];k==e>exit(p);P+=[p+[[x+a,y+b]]for a,b in((0,1),(0,-1),(1,0),(-1,0))if([x+a,y+b]in o)==0<=x+a<N>y+b>-1]

Wypróbuj online!

Haskell , 133 131 130 bajtów

• -1 bajt dzięki BWO

(n!p)o=head.(>>=filter(elem p)).iterate(\q->[u:v|v@([x,y]:_)<-q,u<-[id,map(+1)]<*>[[x-1,y],[x,y-1]],all(/=u)o,x`div`n+y`div`n==0])

Wypróbuj online! (z kilkoma testami)

Funkcja !przyjmująca jako dane wejściowe

• n :: Int rozmiar siatki
• p :: [Int] pozycja gracza jako lista [xp, yp]
• o :: [[Int]] pozycja przeszkód jako lista [[x1, y1], [x2, y2], ...]
• t :: [[[Int]]](domyślnie) pozycja celu jako lista [[[xt, yt]]](lista potrójna dla wygody)

i zwracając prawidłową ścieżkę jako listę [[xp, yp], [x1, y1], ..., [xt, yt]].

Jako bonus znajduje jedną z najkrótszych ścieżek i działa na dowolnej pozycji gracza i celu. Z drugiej strony jest bardzo nieefektywny (ale podane przykłady działają w rozsądnym czasie).

Wyjaśnienie

(n ! p) o =                                                         -- function !, taking n, p, o and t (implicit by point-free style) as input
    head .                                                          -- take the first element of
    (>>= filter (elem p)) .                                         -- for each list, take only paths containing p and concatenate the results
    iterate (                                                       -- iterate the following function (on t) and collect the results in a list
        \q ->                                                       -- the function that takes a list of paths q...
            [u : v |                                                -- ... and returns the list of paths (u : v) such that:
                v@([x, y] : _) <- q,                                -- * v is an element of q (i.e. a path); also let [x, y] be the first cell of v
                u <- [id, map (+ 1)] <*> [[x - 1,y], [x, y - 1]],   -- * u is one of the neighbouring cells of [x, y]
                all (/= u) o,                                       -- * u is not an obstacle
                x `div` n + y `div` n == 0                          -- * [x, y] is inside the grid
            ]
    )

iterate$k$$k-1$[[xt, yt]]

Pozornie niejasne wyrażenie [id, map (+ 1)] <*> [[x - 1,y], [x, y - 1]]jest po prostu „golfową” (-1 bajtową) wersją [[x + 1, y], [x, y + 1], [x - 1, y], [x, y - 1]].

Retina 0.8.2 , 229 bajtów

.
$&$&
@@
s@
##
.#
{`(\w.)\.
$1l
\.(.\w)
r$1
(?<=(.)*)\.(?=.*¶(?<-1>.)*(?(1)$)\w)
d
}`\.(?=(.)*)(?<=\w(?(1)$)(?<-1>.)*¶.*)
u
+T`.`#`.(?=(.)*)(?<=d#(?(1)$)(?<-1>.)*¶.*)|(?<=(.)*.).(?=.*¶(?<-2>.)*(?(2)$)u#)|(?<=#r).|.(?=l#)
.(.)
$1

Wypróbuj online! Nie jestem pewien, czy kwalifikuje się format we / wy. Wyjaśnienie:

.
$&$&

Duplikuj każdą komórkę. Lewa kopia służy jako tymczasowy obszar roboczy.

@@
s@

Oznacz początek labiryntu jako odwiedzony.

##
.#

Oznacz koniec labiryntu jako pusty.

{`(\w.)\.
$1l
\.(.\w)
r$1
(?<=(.)*)\.(?=.*¶(?<-1>.)*(?(1)$)\w)
d
}`\.(?=(.)*)(?<=\w(?(1)$)(?<-1>.)*¶.*)
u

Chociaż istnieją dostępne działające komórki, skieruj je do sąsiednich wcześniej odwiedzonych komórek.

+T`.`#`.(?=(.)*)(?<=d#(?(1)$)(?<-1>.)*¶.*)|(?<=(.)*.).(?=.*¶(?<-2>.)*(?(2)$)u#)|(?<=#r).|.(?=l#)

Śledź ścieżkę od wyjścia do początku, używając komórek roboczych jako wskazówek.

.(.)
$1

Usuń działające komórki.

JavaScript, 450 bajtów

Pobiera dane wejściowe jako (n, {playerx, playery}, {targetx, targety}, [{obstaclex, obstacley}]). Zwraca tablicę {hopx, hopy}.

j=o=>JSON.stringify(o);l=a=>a.length;c=(a,o)=>{let i=l(a);while(i>0){i--;if(j(a[i])==j(o)){return 1;}}return 0;}h=(p,t,o)=>{if(p.y<t.y&&!c(o,{x:p.x,y:p.y+1})){return{x:p.x,y:p.y+1};}if(p.y>t.y&&!c(o,{x:p.x,y:p.y-1})){return{x:p.x,y:p.y-1};}if(p.x<t.x&&!c(o,{x:p.x+1,y:p.y})){return{x:p.x+1,y:p.y};}if(p.x>t.x&&!c(o,{x:p.x-1,y:p.y})){return{x:p.x-1,y:p.y};}return t;}w=(n,p,t,o)=>{let r=[];r.push(p);while(j(p)!==j(t)){p=h(p,t,o);r.push(p);}return r;}

Oto nieobjawiona wersja mojego bałaganu:

// defining some Array's function for proper comparaisons
json = (object) => { return JSON.stringify(object) };
length = (array) => { return array.length; }
contains = (array, object) => {
    let i = length(array);
    while (i > 0) {
    i--;
        if (json(array[i]) == json(object)) { return true; }
    }
    return false;
}
//return next found hop
getNextHop = (player, target, obstacles) => {
    //uggly serie of conditions
    //check where do we have to go and if there is an obstacle there
    if(player.y<target.y && !contains(obstacles, [x:player.x, y:player.y+1])) { return [x:player.x, y:player.y+1]; }
    if(player.y>target.y && !contains(obstacles, [x:player.x, y:player.y-1])) { return [x:player.x, y:player.y-1]; }
    if(player.x<target.x && !contains(obstacles, [x:player.x+1, y:player.y])) { return [x:player.x+1, y:player.y]; }
    if(player.x>target.x && !contains(obstacles, [x:player.x-1, y:player.y])) { return [x:player.x-1, y:player.y]; }
    return target;
}
//return found path
getPath = (gridsize, player, target, obstacles) => {
    let path = [];
    path.push(player);
    //while player is not on target
    while(json(player)!=json(target)) {
        player = getNextHop(player, target, obstacles); //gridsize is never used as player and target are in the grid boundaries
        path.push(player);
    }
    return path;
}