Étant donné un labyrinthe sur stdin et un point d'entrée, écrivez un programme qui imprime un chemin d'accès à la sortie sur stdout. Tout chemin est acceptable, tant que votre programme ne génère pas le chemin trivial (passant par chaque point du labyrinthe) pour chaque labyrinthe.

Dans l'entrée, les murs sont marqués par un #et le point d'entrée par un @. Vous pouvez utiliser n'importe quel caractère pour dessiner le labyrinthe et le chemin dans la sortie, tant qu'ils sont tous distincts.

Vous pouvez supposer que:

• Les points d'entrée et de sortie sont sur les bords de l'entrée
• Chaque ligne de l'entrée a la même longueur
• Le labyrinthe est soluble et n'a pas de cycles
• Il n'y a qu'un seul point de sortie

La solution la plus courte par le nombre de caractères (Unicode) gagne.

Exemples

(notez que les entrées sont remplies d'espaces)

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

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

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

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

Ruby 1.9, 244 caractères

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

Sortie pour les deux exemples:

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

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

Modifications:

• (247 -> 245) Inline e et renommé g
• (245 -> 249) Correction d'un bug lorsque la sortie se trouve directement au-dessus de l'entrée
• (249 -> 246) Inline + simplifications
• (246 -> 244) Manière plus courte d'itérer sur chaque champ

ANSI C ( 384 373 368 caractères)

Voici ma tentative C. Compilé et exécuté sur 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);}

Exemple de sortie pour quelques tests:

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

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

Limitations: ne fonctionne que pour les labyrinthes jusqu'à 1 000 caractères, mais cela peut facilement être augmenté. Je viens de choisir un nombre arbitraire plutôt que de prendre la peine de malloc / remalloc.

En outre, c'est le code le plus chargé d'avertissements que j'ai jamais écrit. 19 avertissements, bien que cela ressemble encore plus à la mise en évidence du code XCode. :RÉ

EDITS: édité et testé pour supprimer int de main, pour utiliser ~ au lieu de! = EOF et putchar au lieu de printf. Merci pour les commentaires!

Python, 339 caractères

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)

Génère un chemin le plus court à travers le labyrinthe.

Sortie par exemple des labyrinthes:

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

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

Python - 510 421 caractères

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 octets

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

Essayez-le en ligne!

Port de ma réponse à Trouver l'itinéraire le plus court sur une route ASCII .

Utilise '#'pour le début, '*'pour la fin, '@'pour le mur et ' 'pour l'espace vide. En cela, la fonction qest une fonction d'aide qui renvoie un tableau unidimensionnel avec le chemin le plus court dans le labyrinthe. La fonction fpeut être raccourcie de 4 octets en n'affectant pas la variable s. Ceci est incroyablement inefficace et expirera probablement, car il appelle la fonction de recherche de chemin pour chaque personnage du labyrinthe.