Ваш друг рассказал вам, как добраться до лучшего ресторана в городе. Это серия левого и правого поворотов. К сожалению, они забыли упомянуть, как долго нужно идти прямо между этими поворотами. К счастью, у вас есть карта улиц со всеми ресторанами. Может быть, вы можете выяснить, какой ресторан они имели в виду?

вход

Карта представлена ​​в виде прямоугольной сетки символов ASCII. .это дорога, #это здание, Aв котором Zнаходятся различные рестораны. Вы начинаете в верхнем левом углу, идете на восток. Пример:

.....A
.#.###
B....C
##.#.#
D....E
##F###

Инструкции вашего друга будут представлены в виде (потенциально пустой) строки или списка символов, содержащих Ls и Rs.

Выход

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

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

Вы должны вывести все рестораны, к которым можно добраться по инструкциям вашего друга, в виде строки или списка.

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

Некоторые примеры для приведенной выше карты:

<empty> A
R       F
RR      B,D
RL      C,E
RLRL    E
RLLR    C
RLLL    B
RLRR    D
RLRRRR  A,C
RLLLRLL B

Обратите внимание, в частности, что Rне достигает B.

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

Применяются стандартные правила игры в гольф .

Дополнительные тестовые случаи

Вот карта большего размера, любезно предоставленная Конором О'Брайеном (который я немного изменил):

.......Y..........................######
.####.....#.##....##..######....#.###.##
B.........#.##.#..##....##...##.#.#P...#
.#.#####..#.##..#.##....##.#....#.####.#
.#.#...C..#.##...G##..#.##.#....#.#....#
.#.#.#.#..#.####.###.#..##.#....#.#.NO.#
.#.#A#.#..#.##...F###...##.#.##.#......#
.#.###....#.##....##....##.#....###....#
.#.....##...##....##...D##........###R.#
.#.##..##...##E...##..######....####...#
.....X....#.#.....................##S.T#
###########.###########M############...#
#................................###.#.#
#.#########.########.######.#.######.#.#
#......V#.....######.IJ...........##.#.#
#########.###......ZH############L##.#.#
#########.##########.###############.#.#
####K##...##########.#....#..........#.#
####....########U......##...#######Q.#.#
#####################################W.#

А вот несколько избранных списков направлений и их ожидаемых результатов:

<empty>                                 Y
RR                                      B
RLL                                     Y
RLRR                                    B,C,X
RLLLRRR                                 G
RLRLRLRL                                I,Z
RLLRRRLRRLRR                            C,D,F,G,Y
RLRRLLRLLLRL                            B,C,Y
RLLRRLRRRLLLL                           F,M,N,O,Y
RLRRLLLRRRRLLLL                         F,M,Y
RLRRLRRRRRRRRRR                         E,F,Y
RLRRRLLLRLLRRLL                         M,N,O
RLLRRLRRLRLRLRRLLR                      E,U
RLRLLRLRRLRRRRRLRL                      F,G,I,Z
RLLRRLLRLLRRRLRRLLRR                    W
RLLLRRRLRRLLLLLRLLLLLL                  D,G,X
RLRLLRLRRLRLRRRLRLLLRR                  B,C,E,J,X
RLRLRLLLLRLRRRRRRLRLRRLR                Y
RLRLRRRLRLLLLRLRRLLLLRLLRRL             E,M,X
RLRLLLRRRLLLRLLRLLRLRRLRLRR             B,E,F,K
RLRRRLLLLLLLLLLLLLLLRRRRLLL             A,B

Бонусный вопрос: есть вход, который приводит только I или только U ? Если да, то какой самый короткий путь?

Perl, 150 149 146 145 141 140 138 136 135 133 130 126 125 124

Добавлено +7 для -F -Xn0i

Начальная попытка.

Запустите с картой на STDIN и указаниями после опции -i, например

perl -F -Xn0iRL incomplete.pl
.....A
.#.###
B....C
##.#.#
D....E
##F###

Закройте STDIN с ^Dили ^Zили что-либо работает в вашей операционной системе.

incomplete.pl:

%P=0;$^I=~s``{%;=!/
/;%P=map{$_|=$F[$^H=$_+=(1,@+,-1,"-@+")[$d&3]]=~/(\w)|#|^$/*~!\$;{$1}}(%P)x@F}$d-=B&$'^u`eg;print%

Замените ^ H буквальным символом управления, чтобы получить данный счет

Бонусный вопрос:

• Нет входных данных, которые приводят только к I
• Кратчайшее вход , который приводит только UэтоRLLRRLLRLRLRRLRRLRLRLRRLLR
• Самый длинный ввод, необходимый для создания уникального набора, RLLRRRLRLRLLLRRLRLLLLLRRRLLRRRLLLLLLLRRLRRRRдаетB O R

Python 2, 180 177 168 163 161 158 байт

def a(v,o,c=0,A=0,d='.',O={0}):
 while'.'==d:w=v.find('\n');c+=[1,~w,-1,w+1][A%4];d=v[c];o>v<a(v+' '*w,o[1:],c,ord(o[0])-~A,d);d>v>o<O.add(d)
 return`O`[9::5]

Параметр v- это карта в виде строки; oэто LRстрока

Митч Шварц сохранил 2 3 10 лотов байтов. Благодарность!

Я сохранил два байта установкой O={0}и возвратом `O`[9::5], что может быть не очень переносимым: hash(0) == 0я полагаю, что это предполагает , что порядок элементов repr(O)должен быть

set([0, 'A', 'B', 'C'])

и творчески разрезая эту строку, я получаю ответ.

C ++ 465

C ++ такой многословный ...

#include <vector>
#include <iostream>
using namespace std;
#define M m[y][x]
#define A if(M!=46)break
vector<string>m;char n[99];int r(int x,int y,int z,const char *d){for(;;){if(z%2)y=y-2+z;else x=x+1-z;if(y<0||y>=m.size()||x<0||x>=m[y].size())break;if(*d){A;r(x,y,(*d==82?z+3:*d==76?z+1:z)%4,d+1);}else{if(M>64&&M<91)n[M]++;A;}}}int main(int c,char**v){string l;while(getline(cin,l))m.push_back(l);r(0,0,0,c>1?v[1]:"");for(char j=0;j<99;j++)if(n[j])cout<<j<<" ";}

Я постараюсь сократить его дальше. Предложения приветствуются.