Dado um quadrado de números naturais positivos, escreva um programa que encontre um caminho horizontal e vertical com a soma dos números ao longo deles sendo máxima. Um caminho horizontal vai da primeira coluna para a última e precisa aumentar a posição da coluna em um em cada etapa. Um caminho vertical vai da primeira linha à última e precisa aumentar sua posição da linha em um em cada etapa. Além disso, a posição da linha em um caminho horizontal pode permanecer a mesma ou mudar uma em qualquer direção, da mesma forma para os caminhos verticais.

Para ilustrar, o seguinte pode ser um caminho válido:

O caminho a seguir seria inválido, pois retrocede (e permanece na mesma linha em alguns lugares):

O caminho a seguir seria igualmente inválido, pois altera a posição da linha em mais de um em uma única etapa:

Nota: A solução deve ser executada em um período de tempo aceitável.

Entrada

n linhas de entrada com n inteiros positivos separados por espaço são dadas na entrada padrão. 2 ≤ n ≤ 40. Cada linha é terminada por uma quebra de linha. Os números são pequenos o suficiente para que a soma máxima caiba em um número inteiro assinado de 32 bits.

Resultado

As somas máximas dos caminhos horizontais e verticais (nessa ordem) separadas por um único espaço.

Entrada de amostra 1

1 2
1 2

Saída de amostra 1

3 4

Entrada de amostra 2

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 4 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 4 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Saída de amostra 2

37 35

Entrada de amostra 3

683 671 420 311 800 936
815 816 123 142 19 831
715 588 622 491 95 166
885 126 262 900 393 898
701 618 956 865 199 537
226 116 313 822 661 214

Saída de amostra 3

4650 4799

Para sua conveniência, preparamos alguns casos de teste no bash (graças ao Ventero ) e no PowerShell, nos quais você pode executar seu programa. A invocação é:, <test> <command line>então algo como ./test python paths.pyou ./test.ps1 paths.exe. Diverta-se :-)

GolfScript - 49 caracteres aprimorados Nabb

51 caracteres
50 caracteres estritamente e absolutamente necessários + 3 preguiçosos que executaram apenas 1
56 caracteres principalmente redundantes

n%{~]}%.zip{{0@+\{\.1>\3<$-1=@+}%\;}*$-1=\}2*' '@

51 solução:

n%{~]}%.zip{(\{0@+\{\.1>\3<$-1=@+}%\}%;$-1=\}2*' '@

53 solução:

n/{~]}%);.zip{(\{0@+\{\.1>\3<$-1=@+}%\}%;$-1=\}2*' '@
             a8_b9___c10___11______12 13      14_

O método funciona em duas linhas por vez, uma contendo as somas máximas atingidas em cada ponto e outra contendo a próxima linha.

a / 14: repita duas vezes, uma vez para cada resultado.
8: Pegue a primeira linha da entrada e troque-a por trás da matriz de entrada, agora no primeiro conjunto de somas máximas.
b / 13: itera sobre cada linha restante na matriz.
9: Coloque 0 no início das somas máximas.
c / 12: itera sobre cada elemento da linha.
10: Faça uma cópia das somas máximas com o primeiro elemento removido.
11: Pegue os 3 primeiros elementos das somas máximas, classifique-os e adicione o maior ao elemento atual da linha.

56 solução:

n/{~]}%);.zip{1,99*\{{\.1>\3<$-1=@+}%0\+\}%;$-1=\}2*' '@
1________2___ 3____ 4______________________5_____ 6_7___

1: Da entrada à matriz de matrizes em 9 caracteres, na verdade isso poderia ter sido feito com apenas 1, mas quebrei essa chave para que isso seja necessário.
2: 4 caracteres apenas para fazer uma cópia transposta.
3: Matriz de 99 0s em 5 caracteres, provavelmente poderia ser feita de uma maneira mais inteligente, mas eu fumo muita maconha para descobrir como.
4: Loop duplo excessivamente complicado que itera sobre todos os elementos da entrada e faz alguma lógica nebulosa ou algo parecido para produzir o resultado. O Nabb provavelmente criará algo equivalente em cerca de 3½ caracteres.
5: A essa altura, o resultado já está lá, dentro de uma matriz, esse código bobo está lá para tirá-lo (e colocar um monte de sobras de lixo (e colocar o resultado no lugar)).
6: Este é um comando tão simples que sua contagem de caracteres provavelmente seria negativa em uma solução ideal. 7: Neste ponto, o programa está realmente pronto, mas devido à falta de clareza no código anterior, a saída está na ordem errada e falta espaço, então aqui vamos mais alguns bits pelo ralo.

J, 91 95

a=:".;._2(1!:1)3
c=:4 :'>./x+"1|:y,.(1|.!.0 y),._1|.!.0 y'
p=:[:>./c/
(":(p|:a),p a)1!:2(4)

Recuso-me a fazer IO, diminuindo drasticamente minha pontuação. Passa em todos os testes no equipamento de teste (embora só funcione se a entrada terminar com uma linha finalizada, como no equipamento de teste).

Eu removi a manipulação das terminações de linha do Windows, pois Chris sugeriu que não era necessário. A versão multiplataforma teria a=:".;._2 toJ(1!:1)3como primeira linha.

Explicação:

• ffornece o par de soluções chamando p normalmente e com a entrada transposed ( |:).
• ptira o máximo ( >./) dos totais de linhas da aplicação centre cada linha ( c/)
• cocupa duas linhas (x e y). Ele adiciona x a cada um de y, y aumentou 1 célula ( 1|.!.0 y) e y reduziu 1 célula ( _1|.!.0 y). Em seguida, são necessários os máximos das três alternativas para cada linha. ( >./) O resto é rank [sic] - não tenho certeza se estou fazendo certo.

Haskell: 314 caracteres necessários

import Data.Vector(fromList,generate,(!))
import List
l=fromList
x=maximum
g=generate
p a=show$x[m!i!0|i<-[0..h-1]]where{
w=length$head a;h=length$a;n=l$map l a;
m=g h$ \i->g w$ \j->n!i!j+x[k#(j+1)|k<-[i-1..i+1]];
i#j|i<0||i>=h||j>=w=0|1>0=m!i!j;}
q a=p a++' ':(p.transpose)a
main=interact$q.map(map read.words).lines

Nota: isso requer o módulo Data.Vector . Não tenho certeza se ele está incluído na plataforma Haskell ou não.

Versão não destruída:

import Data.Vector(fromList,generate,(!))
import Data.List

-- horizontal; we use transpose for the vertical case
max_path :: [[Integer]] -> Integer
max_path numbers = maximum [m ! i ! 0 | i <- [0..h-1]] where
    w = length (head numbers)
    h = length numbers
    n = fromList $ map fromList numbers
    m = generate h $ \i -> generate w $ \j ->
        n ! i ! j + maximum [f i' (j+1) | i' <- [i-1..i+1]]
    f i j | i < 0 || i >= h || j >= w = 0
    f i j = m ! i ! j

max_paths :: [[Integer]] -> String
max_paths numbers = (show . max_path) numbers ++ " " ++
                    (show . max_path . transpose) numbers

main = interact $ max_paths . map (map read . words) . lines

Esta solução usa preguiça, em conjunto com o Data.Vector , para memorização. Para cada ponto, a solução para o caminho máximo desde o final até o final é calculada e, em seguida, armazenada na célula de Vector me reutilizada quando necessário.

Ruby 1.9, 155 caracteres

f=->t{(1...l=t.size).map{|a|l.times{|b|t[a][b]+=t[a-1][(b>0?b-1:0)..b+1].max}};t[-1].max};q=[*$<].map{|a|a.split.map &:to_i};puts [f[q.transpose],f[q]]*" ""

Solução simples que passa em todos os casos de teste.

Haskell, 154 caracteres

import List
z=zipWith
f=show.maximum.foldl1(\a->z(+)$z max(tail a++[0])$z max(0:a)a)
q a=f(transpose a)++' ':f a
main=interact$q.map(map read.words).lines

• Editar: (155 -> 154) alinhava a função dobrada

J, ^{109 + 10 =} 119 caracteres

y=:0".(1!:1)3
N=:%:#y
y=:y$~N,N
r=:(((1&{)(+(3>./\0,0,~]))(0&{)),2&}.)^:(<:N)
(":([:>./"1([:r|:),r)y)(1!:2)4

Corra com tr:

cat << EOF | tr \\n ' ' | ./maxpath.ijs

Como de costume em J, a maior parte do código é para entrada / saída. O código "real" tem 65 caracteres:

r=:(((1&{)(+(3>./\0,0,~]))(0&{)),2&}.)^:(<:#y)
([:>./"1([:r|:),r)y

Passa em todos os casos de teste

Python, 149

import sys
def f(g,t=[]):
 for r in g:t=[int(e)+max(t[i-1:i+2]+[0])for i,e in enumerate(r)]
 print max(t),
g=map(str.split,sys.stdin)
f(zip(*g)),f(g)

Se eu calculasse apenas um caminho mais curto vertical ou horizontal,
isso poderia ser feito no local, economizando cerca de um terço dos bytes.

Python, 204 caracteres

import sys
I=sys.stdin.read()
n=I.count('\n')
A=map(int,I.split())
R=range(n)
X=lambda h,a:[a[i]+max(([0]+h)[i:i+3])for i in R]
h=v=[0]*n
for i in R:h=X(h,A[i*n:i*n+n]);v=X(v,A[i::n])
print max(v),max(h)