Anda adalah pengusaha kereta api di Amerika Serikat abad ke-19 ketika kereta menjadi populer karena mereka adalah sarana paling efisien untuk mengangkut material dalam volume besar melalui darat. Ada kebutuhan nasional untuk rel kereta api dari pantai timur melalui beberapa tanah yang baru saja dijajah di barat.

Untuk mengakomodasi kebutuhan ini, pemerintah AS akan memungut pajak untuk mensubsidi jalur kereta api. Mereka telah berjanji untuk membayar uang kepada perusahaan kereta api Anda untuk setiap mil jalur yang dilalui. Karena meletakkan trek di daerah berbukit dan pegunungan lebih mahal daripada meletakkan trek di tanah datar, mereka menyesuaikan jumlah yang mereka berikan sesuai. Artinya, pemerintah akan membayar

• $ 5.000 per mil trek diletakkan di tanah datar
• $ 12.500 per mil trek diletakkan di tanah berbukit
• $ 20.000 per mil trek diletakkan di pegunungan.

Tentu saja, rencana ini tidak secara akurat mencerminkan berapa biaya sebenarnya untuk meletakkan trek.

Anda telah menyewa beberapa kartografer untuk menggambar peta bantuan dari wilayah tempat Anda akan meletakkan jalur untuk menganalisis ketinggian. Berikut ini salah satu peta tersebut:

S12321
121234
348E96

Setiap digit mewakili satu mil persegi tanah. Sadalah titik awal, Eadalah titik akhir. Setiap angka mewakili intensitas perubahan ketinggian di wilayah itu.

• Tanah bernomor 1-3 merupakan tanah datar.
• Tanah bernomor 4-6 merupakan tanah berbukit.
• Tanah bernomor 7-9 merupakan barisan pegunungan.

Anda, selama bertahun-tahun membangun rel kereta api, menilai bahwa biaya pembuatan rel (dalam dolar) memenuhi formula ini:

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

Itu berarti membangun pada gradien ketinggian tertentu akan dikenakan biaya lebih banyak uang daripada yang diberikan pemerintah, kadang-kadang akan menguntungkan, dan kadang-kadang Anda hanya akan mencapai titik impas.

Misalnya, satu mil trek pada gradien ketinggian 3 membutuhkan biaya $ 8.000 untuk membangun, tetapi Anda hanya dibayar $ 5.000 untuk itu, sehingga Anda kehilangan $ 3000. Sebaliknya, membangun satu mil trek pada gradien elevasi 7 berharga $ 14.000, tetapi Anda dibayar $ 20.000 untuk itu: untung $ 6.000!

Berikut adalah contoh peta, serta dua jalur yang mungkin berbeda.

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

Jalur pertama biaya $ 30.000 untuk membangun, tetapi pemerintah membayar Anda $ 30.000 untuk itu. Anda tidak mendapat untung dari trek ini.

Di sisi lain, yang kedua biaya $ 56.500 untuk membangun, tetapi Anda dibayar $ 62.500 untuk itu. Anda mendapat untung $ 6.000 dari trek ini.

Tujuan Anda: diberi peta bantuan, temukan jalur yang paling menguntungkan (atau mungkin hanya yang paling murah) dari awal hingga akhir. Jika banyak jalur mengikat, salah satunya adalah solusi yang dapat diterima.

Detail Program

Anda diberi input teks yang dipisahkan dengan peta angka persegi panjang dan satu titik awal dan akhir. Setiap angka akan menjadi bilangan bulat secara inklusif antara 1 dan 9. Selain itu, input dapat diberikan sesuai keinginan Anda, sesuai alasan.

Output harus dalam format yang sama dengan input, dengan angka-angka di mana trek telah dibangun digantikan oleh hash ( #). Karena peraturan sewenang-wenang yang diberlakukan oleh beberapa politisi yang berubah-ubah, jalur hanya bisa berjalan secara horizontal atau vertikal. Dengan kata lain, Anda tidak dapat mundur atau pergi secara diagonal.

Program harus dapat menyelesaikan dalam jumlah waktu yang wajar (yaitu <10 menit) untuk peta hingga 6 baris dan 6 kolom.

Ini adalah tantangan kode golf , sehingga program terpendek menang.

Saya punya contoh implementasi (non-golf) .

Contoh I / O

S12321
121234
348E96

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



S73891
121234
348453
231654
97856E

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

Python, 307 karakter

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,

Pmengambil jalan sebagian pdan mengembalikan semua cara untuk memperpanjangnya E. Setiap jalur yang dikembalikan dipasangkan dengan nilainya sehingga maxdapat menemukan yang terbaik.

Memakan waktu sekitar 80 detik pada peta 6x6.

Python: 529 482 460 byte

Solusi saya tidak akan memenangkan hadiah apa pun. Namun, karena hanya ada dua solusi yang diposting dan saya menemukan masalah yang menarik, saya memutuskan untuk tetap mengirim jawaban saya.

Sunting: Terima kasih kepada Howard untuk rekomendasinya. Saya telah berhasil mencukur banyak skor saya!

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 karakter

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]

Pendekatan Ruby Brute-force yang berjalan dengan baik di dalam batasan waktu pada papan 6x6. Masukan harus diberikan pada STDIN.

Contoh:

S12321
121234
348E96

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

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