Dado un laberinto en stdin y un punto de entrada, escriba un programa que imprima una ruta a la salida en stdout. Cualquier ruta es aceptable, siempre que su programa no genere la ruta trivial (pasando por cada punto del laberinto) para cada laberinto.

En la entrada, las paredes están marcadas por a #y el punto de entrada por a @. Puedes usar cualquier personaje para dibujar el laberinto y la ruta en la salida, siempre que sean distintos.

Puede suponer que:

• Los puntos de entrada y salida están en los bordes de la entrada.
• Cada línea de la entrada tiene la misma longitud
• El laberinto es solucionable y no tiene ciclos.
• Solo hay un punto de salida

La solución más corta por recuento de caracteres (Unicode) gana.

Ejemplos

(tenga en cuenta que las entradas están rellenadas con espacios)

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

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

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

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

Ruby 1.9, 244 caracteres

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

Salida para los dos ejemplos:

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

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

Ediciones:

• (247 -> 245) En línea e e renombró a g
• (245 -> 249) Repara un error cuando la salida está directamente encima de la entrada
• (249 -> 246) Inline + simplificaciones
• (246 -> 244) Forma más corta de iterar sobre cada campo

ANSI C ( 384 373 368 caracteres)

Aquí está mi intento de C. Compilado y ejecutado en 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);}

Salida de muestra para un par de pruebas:

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

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

Limitaciones: solo funciona para laberintos de hasta 1000 caracteres, pero esto se puede aumentar fácilmente. Acabo de elegir un número arbitrario en lugar de molestarme con malloc / remalloc.

Además, este es el código más cargado de advertencia que he escrito. 19 advertencias, aunque parece aún más con el resaltado del código XCode. :RE

EDITOS: Editado y probado para soltar int desde main, para usar ~ en lugar de! = EOF y putchar en lugar de printf. ! Gracias por los comentarios!

Python, 339 caracteres

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)

Genera un camino más corto a través del laberinto.

Salida, por ejemplo, laberintos:

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

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

Python - 510 421 caracteres

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

Pruébalo en línea!

Puerto de mi respuesta para encontrar la ruta más corta en una carretera ASCII .

Usos '#'para inicio, '*'fin, '@'pared y ' 'espacio vacío. En esto, la función qes una función auxiliar que devuelve una matriz unidimensional con la ruta más corta en el laberinto. La función fse puede acortar 4 bytes al no asignar la variable s. Esto es increíblemente ineficiente y probablemente superará el tiempo de espera, ya que llama a la función de búsqueda de ruta para cada personaje en el laberinto.