C++ 292

Thanks to @ceilingcat for finding a much better (and shorter) version

#import<iostream>
#define M m[y][x]
char m[99][99],n[99],j,q;int r(int x,int y,char*d,int z){for(;z%2?y+=z-2:x-=z-1,y<q&&~x*M*!*d|M==46&&(!*d?n[M]+=M-65<26u,M==46:!r(x,y,d+1,z+(*d-82?*d==76:3)&3)););}main(int,char**v){for(;std::cin>>m[q++];);for(r(0,0,v[1],0);j<99;j++)n[j]&&printf("%c ",j);}

Try it online!

Haskell, 257 bytes

import Data.List
t=transpose
r=reverse
l=length
f(m,x,y)=[(m,n,y)|n<-[x+1..l(m!!0)-1],notElem '#'[m!!y!!z|z<-[x..n]]]
i!c=[last$(t.r$m,l m-y-1,x):[(r.t$m,y,l(m!!0)-x-1)|c/='L']|(m,x,y)<-i>>=f]
m#i=intersect['A'..'Z'][a!!y!!x|(a,x,y)<-foldl(!)[(m,0,0)]i>>=f]

Try it Online!

Calling m#i for a map m with a list of instructions i outputs the possible restaurants.

Python3, 333 bytes:

m,n={1:{0:3,1:4},2:{0:4,1:3},3:{0:2,1:1},4:{0:1,1:2}},{1:(0,1),2:(0,-1),3:(1,0),4:(-1,0)}
def f(b,p,x,y,d):
 try:
   if b[x][y]=='.':
    x+=n[d][0];y+=n[d][1]
    if 64<ord(r:=b[x][y])<91 and not p:yield r
    if x>=0and y>=0:yield from f(b,p,x,y,d);yield from f(b,p[1:],x,y,m[d][p[0]=='L'])
 except:1
q=lambda b,p:set(f(b,p,0,0,1))

Try it online!

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

Added +7 for -F -Xn0i

An initial attempt.

Run with the map on STDIN and the directions after the -i option, e.g.

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

Close STDIN with ^D or ^Z or whatever works on your operating system.

incomplete.pl:

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

Replace the ^H by the literal control character to get the given score

Bonus question:

• There is no input that results in only I
• The shortest input that results in only U is RLLRRLLRLRLRRLRRLRLRLRRLLR
• The longest input needed to result in a unique set is RLLRRRLRLRLLLRRLRLLLLLRRRLLRRRLLLLLLLRRLRRRR which gives B O R

Python 2, 180 177 168 163 161 158 bytes

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]

Parameter v is the map as a string; o is the LR string.

Mitch Schwartz saved 2 3 10 lots of bytes. Thanks!

I saved two bytes by setting O={0} and returning `O`[9::5], which might not be very portable: it assumes that hash(0) == 0, I think, because that causes the order of elements in repr(O) to be

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

and creatively slicing that string gets me the answer.