Wenn Sie ein Labyrinth auf stdin und einen Einstiegspunkt haben, schreiben Sie ein Programm, das einen Pfad zum Ausgang auf stdout ausgibt. Jeder Pfad ist akzeptabel, solange Ihr Programm nicht den trivialen Pfad (der durch jeden Punkt im Labyrinth verläuft) für jedes Labyrinth generiert.

In der Eingabe sind Wände mit einem #und der Einstiegspunkt mit einem gekennzeichnet @. Sie können beliebige Zeichen verwenden, um das Labyrinth und den Pfad in der Ausgabe zu zeichnen, sofern sie alle unterschiedlich sind.

Sie können davon ausgehen, dass:

• Die Eintritts- und Austrittspunkte befinden sich an den Rändern der Eingabe
• Jede Zeile der Eingabe hat die gleiche Länge
• Das Labyrinth ist lösbar und hat keine Zyklen
• Es gibt nur einen Austrittspunkt

Kürzeste Lösung nach (Unicode) Zeichenzahl gewinnt.

Beispiele

(Beachten Sie, dass die Eingaben mit Leerzeichen aufgefüllt sind)

####   
#  #   
@ #####
#     #
#      
#######

####
#  #
@*#####
#*    #
#******
#######

### ###################
###         #         #
##  #########      #  #
 #             #####  #
 ###############   #@##

###*###################
###*********#*********#
## *#########*     # *#
 # *********** #####**#
 ###############   #@##

Ruby 1.9, 244 Zeichen

l=*$<
i=l*""
e=[]
d=[1,-1,x=l[0].size,-x]
r=[f=9e9]*s=x*b=l.size;r[i=~/@/]=0
r.map{i.gsub(/ /){r[p=$`.size]=d.map{|u|p>-u&&r[u+p]||f}.min+1;e<<p if p%x%~-~-x*(p/-~x%~-b)<1}}
r[g=e.find{|i|r[i]<f}].times{i[g]=?*;g+=d.find{|l|r[g]>r[g+l]}}
puts i

Ausgabe für die beiden Beispiele:

####   
#  #   
@*#####
#*    #
#******
#######

###*###################
###*        #     *** #
## *######### *****#* #
 # ************#####* #
 ###############   #@##

Bearbeitungen:

• (247 -> 245) Inline e und umbenannt in g
• (245 -> 249) Beheben Sie einen Fehler, wenn sich der Ausgang direkt über dem Eingang befindet
• (249 -> 246) Inlining + Vereinfachungen
• (246 -> 244) Kürzere Methode zum Durchlaufen aller Felder

ANSI C ( 384 373 368 Zeichen)

Hier ist mein C-Versuch. Kompiliert und ausgeführt unter Mac OS X.

m[9999],*r=m,*s=m,c,R=0,*a,L;
P(){while(*s++)putchar(*(s-1));}
C(int*l){if((l-s+2)%R==0||(l-s)%R==0||l-s<R||l>r-R)*l=42,P(),exit(0);}
e(int*l){if(*l==32)C(l),*l=42,e(l-1),*l=32,*l=42,e(l-R),*l=32,*l=42,e(l+1),*l=32,*l=42,e(l+R),*l=32;}
main(){while(~(c=getchar()))*r++=c,R=!R&&c==10?r-s:R,L=c==64?r-s-1:L;L%R==0&&e(s+L+1);(L+2)%R==0&&e(s+L-1);L<R&&e(s+L+R);e(s+L-R);}

Beispielausgabe für einige Tests:

####   
#  #   
@*#####
#*****#
#    *#
#####*#

###*###################
###*        #******** #
##**#########**    #* #
 #*************#####* #
 ###############   #@##

Einschränkungen: Funktioniert nur für Labyrinthe mit bis zu 1000 Zeichen, kann jedoch leicht erhöht werden. Ich habe nur eine beliebige Nummer gewählt, anstatt mich um malloc / remalloc zu kümmern.

Außerdem ist dies der Code mit den meisten Warnungen, den ich jemals geschrieben habe. 19 Warnungen, obwohl es mit der Hervorhebung des XCode-Codes noch mehr aussieht. : D

BEARBEITUNGEN: Bearbeitet und getestet, um int von main zu entfernen und ~ anstelle von! = EOF und putchar anstelle von printf zu verwenden. Danke für die Kommentare!

Python, 339 Zeichen

import sys
M=list(sys.stdin.read())
L=len(M)
R=range(L)
N=M.index('\n')+1
D=2*L*[9e9]
D[M.index('@')+N]=0
J=(1,-1,N,-N)
for x in R:
 for i in[N+i for i in R if' '==M[i]]:D[i]=min(1+D[i+j]for j in J)
e=[i+N for i in R[:N]+R[::N]+R[N-2::N]+R[-N:]if 0<D[i+N]<9e9][0]
while D[e]:M[e-N]='*';e=[e+j for j in J if D[e+j]<D[e]][0]
print''.join(M)

Erzeugt einen kürzesten Weg durch das Labyrinth.

Ausgabe zum Beispiel Labyrinthe:

####   
#  #   
@*#####
#*    #
#******
#######

###*###################
###*        #     *** #
## *######### *****#* #
 # ************#####* #
 ###############   #@##

Python - 510 421 Zeichen

m=[]
i=raw_input
l=i()
x=y=-1
while l:
 if y<0:x+=1;y=l.find('@')
 m.append(list(l));l=i()
s=(x,y)
t={}
q=[s]
v={s:1}
while 1:
 try:(i,j),q=q[0],q[1:];c=m[i][j]
 except:continue
 if c==' 'and(i*j==0)|(i+1==len(m))|(j+1==len(m[0])):break
 for d,D in(-1,0),(0,-1),(1,0),(0,1):
  p=(i+d,j+D)
  if not p in v and'#'!=c:v[p]=0;q.append(p);t[p]=(i,j)
while(i,j)!=s:m[i][j]='*';i,j=t[(i,j)]
print'\n'.join(''.join(l)for l in m)

Python 3 , 275 Bytes

import sys
def q(g,s=[]):w=len(g[0])+1;k='@'.join(g)+w*'@';*p,x=s or[k.find('#')];return'@'>k[x]and{x}-{*p}and[p,min((q(g,s+[x+a])or k for a in(-1,1,-w,w)),key=len)]['*'>k[x]]
g=''.join(sys.stdin.read());s=q(g.split('\n'))
for i in range(len(g)):print(end=[g[i],'+'][i in s])

Probieren Sie es online!

Port meiner Antwort auf die Suche nach der kürzesten Route auf einer ASCII-Straße .

Verwendet '#'für Anfang, '*'Ende, '@'Wand und ' 'leeren Raum. In diesem Fall qist die Funktion eine Hilfsfunktion, die ein eindimensionales Array mit dem kürzesten Pfad im Labyrinth zurückgibt. Die Funktion fkann um 4 Bytes gekürzt werden, indem die Variable nicht zugewiesen wird s. Dies ist unglaublich ineffizient und führt wahrscheinlich zu einer Zeitüberschreitung, da die Wegfindungsfunktion für jeden Charakter im Labyrinth aufgerufen wird.