| Bytes | Lang | Time | Link |
|---|---|---|---|
| 426 | Python3 | 240625T001825Z | Ajax1234 |
| 460 | Python | 140317T214244Z | sadakats |
| 233 | Ruby | 140317T150726Z | Howard |
| 307 | Python | 111116T063616Z | Keith Ra |
Python3, 426 bytes
E=enumerate
def f(b):
d={(x,y):int(v)if v.isdigit()else v for x,r in E(b)for y,v in E(r)}
q,e=[(*i,[i],0,0)for i in d if'S'==d[i]],[]
for x,y,p,c,C in q:
for X,Y in[(1,0),(-1,0),(0,-1),(0,1)]:
if(t:=(x+X,y+Y))not in p and t in d:
if'E'==d[t]:e+=[(p,c,C)];continue
if d[t]<4:T=50
elif d[t]>3 and d[t]<7:T=120
else:T=200
q+=[(*t,p+[t],c+50+(15*(d[t]-1)),C+T)]
return max(e,key=lambda x:x[2]-x[1])[0]
Python: 529 482 460 bytes
My solution will not win any prizes. However, since there are only two solutions posted and I found the problem interesting, I decided to post my answer anyway.
Edit: Thanks to Howard for his recommendations. I've managed to shave a lot of my score!
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 characters
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]
A Ruby brute-force approach which runs well inside the time constraints on a 6x6 board. The input must be given on STDIN.
Examples:
S12321
121234
348E96
S#2321
1#####
3##E##
--
S73891
121234
348453
231654
97856E
S#####
1212##
#####3
#3####
#####E
Python, 307 chars
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,
P takes a partial path p and returns all ways of extending it to reach E. Each returned path is paired with its score so max can find the best one.
Takes about 80 seconds on a 6x6 map.