Usted es un empresario ferroviario en los Estados Unidos del siglo XIX cuando los trenes se hicieron populares porque son el medio más eficiente de transportar grandes volúmenes de materiales por tierra. Existe una necesidad nacional de vías de ferrocarril desde la costa este a través de algunas tierras recientemente colonizadas en el oeste.

Para satisfacer esta necesidad, el gobierno de los Estados Unidos impondrá un impuesto para subsidiar los ferrocarriles. Han prometido pagar dinero a su compañía ferroviaria por cada milla de vía establecida. Dado que la colocación de pistas en regiones montañosas y montañosas es más costosa que la colocación de pistas en tierras planas, ajustan la cantidad que dan en consecuencia. Es decir, el gobierno pagará

• $ 5,000 por milla de vía tendida en terreno plano
• $ 12,500 por milla de camino tendido en terreno montañoso
• $ 20,000 por milla de camino tendido en las montañas.

Por supuesto, este plan no refleja con precisión cuánto cuesta realmente establecer pistas.

Ha contratado a algunos cartógrafos para que dibujen mapas en relieve de las regiones en las que realizará el seguimiento para analizar la elevación. Aquí hay uno de esos mapas:

S12321
121234
348E96

Cada dígito representa una milla cuadrada de tierra. Ses el punto de partida, Ees el punto final. Cada número representa la intensidad de los cambios de elevación en esa región.

• La tierra numerada 1-3 constituye tierra plana.
• La tierra numerada 4-6 constituye tierra montañosa.
• La tierra numerada 7-9 constituye una cadena montañosa.

A través de años de experiencia en la construcción de vías férreas, ha evaluado que el costo de la construcción de vías (en dólares) satisface esta fórmula:

Cost_Per_Mile = 5000 + (1500 * (Elevation_Rating - 1))

Eso significa que construir sobre ciertos gradientes de elevación le costará más dinero del que otorga el gobierno, a veces será rentable, y a veces simplemente alcanzará el punto de equilibrio.

Por ejemplo, una milla de pista en un gradiente de elevación de 3 cuesta $ 8,000 para construir, pero solo le pagan $ 5,000 por ella, por lo que pierde $ 3000. En contraste, construir una milla de pista en un gradiente de elevación de 7 cuesta $ 14,000, pero le pagan $ 20,000 por ello: ¡una ganancia de $ 6,000!

Aquí hay un mapa de ejemplo, así como dos posibles caminos diferentes.

S29    S#9    S##
134    1#4    1##
28E    2#E    2#E

La primera pista cuesta $ 30,000 dólares para construir, pero el gobierno le paga $ 30,000 por ella. No obtienes ganancias de esta pista.

Por otro lado, el segundo cuesta $ 56,500 para construir, pero le pagan $ 62,500 por ello. Obtiene $ 6,000 de esta pista.

Su objetivo: dado un mapa en relieve, encuentre el camino más rentable (o quizás simplemente el menos costoso) desde el principio hasta el final. Si se vinculan varias rutas, cualquiera de ellas es una solución aceptable.

Detalles del programa

Se le da entrada de texto separada con un mapa rectangular de números y un punto inicial y final. Cada número será un número entero inclusive entre 1 y 9. Aparte de eso, la entrada puede proporcionarse como desee, dentro de lo razonable.

La salida debe estar en el mismo formato que la entrada, con los números donde la pista ha sido construida reemplazada por un hash ( #). Debido a las regulaciones arbitrarias impuestas por algunos políticos caprichosos, las pistas solo pueden ir en caminos horizontales o verticales. En otras palabras, no puedes retroceder o ir en diagonal.

El programa debería poder resolver en un tiempo razonable (es decir, <10 minutos) para mapas de hasta 6 filas y 6 columnas.

Este es un desafío de código de golf , por lo que gana el programa más corto.

Tengo un ejemplo (no golfizado) de implementación .

Muestra de E / S

S12321
121234
348E96

S12321
######
3##E##



S73891
121234
348453
231654
97856E

S#3###
1###3#
3#####
######
#####E

Python, 307 caracteres

import os
I=os.read(0,99)
n=I.find('\n')+1
I='\0'*n+I+'\0'*n
def P(p):
 S=[]
 for d in(-n,-1,1,n):
  y=p[-1]+d
  if'E'==I[y]:S+=[(sum((int(I[v])-1)/3*75-15*int(I[v])+15for v in p[1:]),p)]
  if'0'<I[y]<':'and y not in p:S+=P(p+[y])
 return S
for i in max(P([I.find('S')]))[1][1:]:I=I[:i]+'#'+I[i+1:]
print I,

Ptoma un camino parcial py devuelve todas las formas de extenderlo para llegar E. Cada ruta devuelta se combina con su puntaje para que maxpueda encontrar la mejor.

Toma alrededor de 80 segundos en un mapa de 6x6.

Python: 529 482 460 bytes

Mi solución no ganará ningún premio. Sin embargo, dado que solo hay dos soluciones publicadas y el problema me pareció interesante, decidí publicar mi respuesta de todos modos.

Editar: Gracias a Howard por sus recomendaciones. ¡Me las arreglé para reducir mi puntaje!

import sys
N=len
def S(m,c,p=0):
 if m[c]=='E':return m,p
 if m[c]<'S':
    b=list(m);b[c]='#';m=''.join(b)
 b=[],-float('inf')
 for z in(1,-1,w,-w):
    n=c+z
    if 0<=n<N(m)and m[n]not in('S','#')and(-2<z<2)^(n/w!=c/w):
     r=S(m,n,p+(0if m[n]=='E'else(int(m[n])-1)/3*5-int(m[n])+1))
     if b[1]<r[1]:b=r
 return b
m=''
while 1:
 l=sys.stdin.readline().strip()
 if l=='':break
 w=N(l);m+=l
b,_=S(m,m.index('S'))
for i in range(0,N(b),w):print b[i:i+w]

Ruby, 233 caracteres

R=->s{o=s=~/S/m
s=~/E/m?(q=[-1,1,-N,N].map{|t|s[f=o+t]>'0'?(n=s*1
n[o]='#'
n[f]='S'
a=R[n]
a&&[a[0]-(e=s[f].to_i-1)/3*5+e,a[1]]):nil}-[nil]
q.sort!&&q[0]):[0,(n=s*1;n[o]='E'
n[$_=~/S/m]='S'
n)]}
N=1+(gets(nil)=~/$/)
$><<R[$_+$/*N][1]

Un enfoque de fuerza bruta de Ruby que funciona bien dentro de las limitaciones de tiempo en un tablero de 6x6. La entrada debe darse en STDIN.

Ejemplos:

S12321
121234
348E96

S#2321
1#####
3##E##    
--    
S73891
121234
348453
231654
97856E

S#####
1212##
#####3
#3####
#####E