Вы являетесь железнодорожным предпринимателем в Соединенных Штатах 19-го века, когда поезда становятся популярными, потому что они являются наиболее эффективным средством транспортировки больших объемов материалов по суше. Существует национальная потребность в железнодорожных путях от восточного побережья через некоторые недавно колонизированные земли на западе.

Чтобы удовлетворить эту потребность, правительство США собирается взимать налог на субсидирование железных дорог. Они обещали заплатить деньги вашей железнодорожной компании за каждую пройденную милю пути. Так как укладка дорожек в холмистых и горных районах обходится дороже, чем укладка дорожек на равнине, они соответственно корректируют количество, которое дают. То есть правительство будет платить

• 5000 долларов за милю трассы, проложенной на равнине
• $ 12500 за милю трассы, проложенной в холмистой местности
• 20 000 долларов за милю трассы, проложенной в горах.

Конечно, этот план не точно отражает, сколько на самом деле стоит заложить треки.

Вы наняли нескольких картографов, чтобы нарисовать рельефные карты регионов, где вы будете прокладывать трассу для анализа высоты. Вот одна из таких карт:

S12321
121234
348E96

Каждая цифра представляет одну квадратную милю земли. Sявляется отправной точкой, Eявляется конечной точкой. Каждое число представляет интенсивность изменений высоты в этом регионе.

• Земля с номерами 1-3 представляет собой равнину.
• Земля с номерами 4-6 составляет холмистую землю.
• Земля с номерами 7-9 составляет горный массив.

По многолетнему опыту строительства железнодорожных путей вы оценили, что стоимость строительства путей (в долларах) удовлетворяет следующей формуле:

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

Это означает, что построение на определенных градиентах будет стоить вам больше денег, чем правительство, иногда это будет выгодно, а иногда вы просто безубыточны.

Например, километр трассы с градиентом возвышения 3 стоит 8000 долларов на строительство, но вам платят только 5000 долларов, поэтому вы теряете 3000 долларов. В отличие от этого, строительство километра трассы с градиентом возвышения, равным 7, стоит 14 000 долларов, но за это вам платят 20 000 долларов: прибыль в 6000 долларов!

Вот пример карты, а также два разных возможных пути.

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

Первый трек стоит 30000 долларов, но правительство платит за него 30000 долларов. Вы не получаете прибыль от этого трека.

С другой стороны, строительство второго стоит 56 500 долларов, но за это вам платят 62 500 долларов. Вы получаете $ 6000 с этого трека.

Ваша цель: с помощью рельефной карты найти наиболее выгодный (или, возможно, просто наименее дорогой) путь от начала до конца. Если несколько путей связаны, любой из них является приемлемым решением.

Детали программы

Вам предоставляется ввод текста, разделенный прямоугольной картой чисел и одной начальной и конечной точкой. Каждое число будет целым числом от 1 до 9. Кроме этого, ввод может быть предоставлен, как вам угодно, в пределах разумного.

Выходные данные должны быть в том же формате, что и входные данные, а номера, в которых была построена дорожка, заменены на hash ( #). Из-за произвольных правил, введенных некоторыми капризными политиками, треки могут идти только по горизонтали или вертикали. Другими словами, вы не можете вернуться назад или идти по диагонали.

Программа должна быть в состоянии решить за разумное время (то есть <10 минут) для карт до 6 строк и 6 столбцов.

Это кодовое соревнование по гольфу , поэтому выигрывает самая короткая программа.

У меня есть пример (не в гольф) реализации .

Образец ввода / вывода

S12321
121234
348E96

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



S73891
121234
348453
231654
97856E

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

Питон, 307 символов

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принимает частичный путь pи возвращает все пути его расширения для достижения E. Каждый возвращаемый путь связан со своим счетом, поэтому maxможно найти лучший.

Занимает около 80 секунд на карте 6х6.

Python: 529 482 460 байт

Мое решение не выиграет никаких призов. Однако, поскольку опубликовано только два решения, и я нашел проблему интересной, я все равно решил опубликовать свой ответ.

Редактировать: Спасибо Говарду за его рекомендации. Мне удалось побрить большую часть моего счета!

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]

Рубин, 233 символа

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]

Рубиновый метод грубой силы, который хорошо работает в условиях ограничения времени на доске 6х6. Ввод должен быть дан на STDIN.

Примеры:

S12321
121234
348E96

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

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