Roguelike поиск пути

Ваша задача будет, учитывая двумерный массив элементов, описанных ниже, который представляет собой подземелье, вывести или вернуть одно число, представляющее количество золотых монет, которые мошенник может собрать, не разбудив никаких монстров.

Элементы массива следующие:

1. Пустые пробелы представлены либо .пробелом, либо вашим вызовом;
2. Стартовая позиция Rogue представлена, конечно @,;
3. Золотой кусок представлен как $;
4. Стены представлены #;
5. Монстры представлены символами из следующего регулярного выражения: [a-zA-Z*&].

Массив не должен содержать никаких символов, не перечисленных выше, поэтому вы можете предположить, что все, что не является стеной, пустым пространством, жуликом или золотым предметом, является монстром.

Правила для поиска пути:

1. Бродяга может проходить только через пустые клетки или клетки, содержащие золото;
2. Для перехода в соседнюю или соседнюю по диагонали клетку требуется поворот;
3. Собирание золота происходит мгновенно;
4. Жулик не может оставаться рядом или по диагонали рядом с монстром более одного хода, не разбудив его, что запрещено;
5. Разбойник может входить в область осознания монстра любое количество раз, монстр проснется только в том случае, если разбойник проводит два последовательных хода рядом с ним.

Правила ввода и вывода

Вы можете получить входные данные в любом приемлемом формате, включая двумерный массив, плоский массив, строку или что-либо еще. Если это облегчает вашу жизнь, вы можете также взять размеры массива.

Гарантируется, что в начале мошенник не будет рядом с монстром.

Полная программа или функция в порядке.

счет

Это код-гольф , счет - количество байтов вашей заявки, причем меньше - лучше.

Контрольные примеры

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

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

Просто тест на вменяемость.

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

Опять тест на вменяемость.

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

Жулик может схватить золото, двигаясь слева.

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

Бродяга может зигзагообразно между монстрами, никогда не оставаясь рядом с каждым более чем на один ход.

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

Тактика из предыдущего контрольного примера здесь не работает - области чувствительности монстров перекрываются.

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

Тест на вменяемость.

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

То же самое.

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

Из всего золота здесь можно безопасно добраться только до трех: золото возле начальной позиции можно получить, переместившись вниз на одну, а затем обратно в исходную позицию. Чтобы сбежать из верхнего левого угла, жулик должен двинуться по диагонали вниз-вправо дважды. Золото в середине не представляет проблемы. Внешнее золото охраняется gи bможет быть получено путем перемещения по диагонали от места справа от среднего золота и затем обратно. Остальное невозможно получить: верхнее правое золото блокируется стенами, а нижнее правое золото требует двух поворотов в областях чувствительности монстров.

Следующие тесты были щедро пожертвованы mbomb007.

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

Этот хитрый. Путь есть b4-b5-c6-b7-c8-b8(grab).

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

Путь есть [bc]4-c5-b6-c7-b8(grab).

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

Дополнительная стена на самом деле ничего не меняет, [bc]4-c5-b6-c7-b8(grab)это все еще решение.

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

JavaScript (Node.js) , 883 436 411 360 345 311 байт

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=="@"}

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

Объяснение -

вместо того, чтобы идти от игрока к наличным деньгам, я пошел от случая к @. я думаю, что должен быть быстрее, потому что я знаю, когда перестать смотреть (дойти до @), и когда вы ищете наличные деньги, вы должны всегда двигаться, пока не пройдете все точки (и способы добраться до них). таким образом, алгоритм довольно прост - основная функция g.map((r,y)=>[...r].map((c,x)=>A+=c=="$"&&P(g,x,y)),A=0)|A: найти деньги -> если вы нашли это -> начать искать игрока -> если вы его нашли -> приращение A теперь позволяет добраться до искателя пути, иначе P if(/[.$]/.test(c=(g[y]||[])[x]))просто проверьте, если текущая ячейка «специальная» -> если так, мы хотим вернуть, если это игрок. особые случаи: @ # (монстр)

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 итерируйте соседей снова - если я еще не был там (p - путь, взятый), продолжить путь (вызов P)