Вызов

Учитывая размер сетки, положение препятствий, положение игрока и положение цели, ваша задача состоит в том, чтобы найти путь для игрока, чтобы добраться до цели и избежать препятствий одновременно (при необходимости).

вход

• N : размер сеткиN x N
• P : позиция игрока[playerposx, playerposy]
• T : позиция цели[targetposx, targetposy]
• O : позиции препятствий[[x1, y1], [x2, y2],...,[xn, yn]]

Выход

Путь : путь, по которому игрок может добраться до цели[[x1, y1], [x2, y2],...,[xn, yn]]

правила

1. Точка [0,0]находится в верхнем левом углу сетки.
2. Положение игрока всегда будет на левой стороне сетки.
3. Положение цели всегда будет на правой стороне сетки.
4. Сетка всегда будет иметь хотя бы одно препятствие.
5. Вы можете предположить, что никакое препятствие не перекрывает игрока или целевую позицию.
6. Вам не обязательно нужно найти минимальный путь.
7. Игрок может двигаться только влево, вправо, сверху и снизу не по диагонали.
8. Вы можете принять вход любым удобным способом.
9. Вы можете предположить, что путь для игрока, чтобы добраться до цели, всегда будет существовать.
10. Очевидно, что для каждого ввода существует несколько допустимых путей, выберите один.
11. Предположим, N > 2что сетка будет как минимум 3 x 3.

Примеры

Входной сигнал: 9, [6, 0], [3, 8], [[0, 5], [2, 2], [6, 4], [8, 2], [8, 7]]
Возможный выход:[[6, 0], [6, 1], [6, 2], [6, 3], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [5, 8], [4, 8], [3, 8]]

Входной сигнал: 6, [1, 0], [3, 5], [[1, 2], [2, 5], [5, 1]]
Возможный выход:[[1, 0], [1, 1], [2, 1], [2, 2], [2, 3], [2, 4], [3, 4], [3, 5]]

Заметка

Обратите внимание, что Xдля строк и Yстолбцов. Не путайте их с координатами на изображении.

редактировать

Как указал @digEmAll, из-за правил #2и #3, playerY = 0и targetY = N-1. Таким образом, если вы хотите, вы можете взять только в качестве входных данных playerXи и targetX(если это делает ваш код короче).

JavaScript (ES6), 135 байт

Принимает ввод как (width, [target_x, target_y], obstacles)(source_x, source_y), где препятствия - это массив строк в "X,Y"формате.

Возвращает массив строк в "X,Y"формате.

(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

Попробуйте онлайн!

комментарии

(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 байт

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)}

Попробуйте онлайн!

Не очень короткий, и определенно не дает кратчайший путь (например, проверьте первый пример).
Он в основном выполняет рекурсивный поиск в глубину и останавливается, как только цель достигнута, печатая путь.

Спасибо JayCe за улучшение форматирования вывода

Python 2 , 151 149 байт

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]

Попробуйте онлайн!

Haskell , 133 131 130 байт

• -1 байт благодаря 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])

Попробуйте онлайн! (с несколькими тестами)

Функция, !принимающая в качестве входных данных

• n :: Int размер сетки
• p :: [Int] позиция игрока в списке [xp, yp]
• o :: [[Int]] позиция препятствий в виде списка [[x1, y1], [x2, y2], ...]
• t :: [[[Int]]](неявная) позиция цели в виде списка [[[xt, yt]]](тройной список просто для удобства)

и возвращает правильный путь в виде списка [[xp, yp], [x1, y1], ..., [xt, yt]].

В качестве бонуса он находит (один из) кратчайший путь и работает на позицию любого игрока и цели. С другой стороны, это очень неэффективно (но приведенные примеры выполняются за разумное время).

объяснение

(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]]

По-видимому, неясное выражение [id, map (+ 1)] <*> [[x - 1,y], [x, y - 1]]- это просто «версия для гольфа» (-1 байт) [[x + 1, y], [x, y + 1], [x - 1, y], [x, y - 1]].

Сетчатка 0.8.2 , 229 байт

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

Попробуйте онлайн! Не уверен, подходит ли формат ввода / вывода. Объяснение:

.
$&$&

Дублируйте каждую клетку. Левая копия используется как временная рабочая зона.

@@
s@

Пометить начало лабиринта как посещенное.

##
.#

Отметьте конец лабиринта как пустой.

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

Пока существуют доступные рабочие ячейки, наведите их на соседние ранее посещенные ячейки.

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

Проследите путь от выхода до начала, используя рабочие ячейки в качестве ориентира.

.(.)
$1

Удалить рабочие ячейки.

JavaScript, 450 байт

Принимает вход как (n, {playerx, playery}, {targetx, targety}, [{obstaclex, obstacley}]). Возвращает массив {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;}

Вот бесподобная версия моего беспорядка:

// 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;
}