Biorąc pod uwagę kwadrat dodatnich liczb naturalnych, napisz program, znajdź ścieżkę poziomą i pionową, a suma liczb wzdłuż nich będzie maksymalna. Pozioma ścieżka przechodzi od pierwszej do ostatniej kolumny i musi zwiększyć swoją pozycję kolumny jednym w każdym kroku. Pionowa ścieżka przechodzi od pierwszego do ostatniego wiersza i musi zwiększyć swoją pozycję wiersza jednym w każdym kroku. Ponadto pozycja rzędu na ścieżce poziomej może pozostać niezmieniona lub zmieniać się o jedną w obu kierunkach, podobnie w przypadku ścieżek pionowych.

Aby to zilustrować, poprawna ścieżka może być następująca:

Następująca ścieżka byłaby nieprawidłowa, ponieważ prowadzi do tyłu (i pozostaje w tym samym rzędzie w niektórych miejscach):

Następująca ścieżka byłaby równie nieprawidłowa, ponieważ zmienia pozycję wiersza o więcej niż jeden w jednym kroku:

Uwaga: Rozwiązanie powinno działać w akceptowalnym czasie.

Wejście

n standardowych linii wejściowych z n dodatnimi liczbami całkowitymi oddzielonymi spacją. 2 ≤ n ≤ 40. Każda linia kończy się przerwaniem linii. Liczby są na tyle małe, że maksymalna suma mieści się w 32-bitowej liczbie całkowitej ze znakiem.

Wynik

Maksymalne sumy poziomych i pionowych ścieżek (w tej kolejności) oddzielone pojedynczym odstępem.

Przykładowe dane wejściowe 1

1 2
1 2

Próbka wyjściowa 1

3 4

Przykładowe wejście 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

Próbka wyjściowa 2

37 35

Przykładowe dane wejściowe 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

Próbka wyjściowa 3

4650 4799

Dla Twojej wygody przygotowaliśmy kilka przypadków testowych w bash (dzięki Ventero ) i PowerShell, przez które możesz uruchomić swój program. Wywołanie to:, <test> <command line>więc coś w stylu ./test python paths.pylub ./test.ps1 paths.exe. Baw się dobrze :-)

GolfScript - 49 ulepszonych postaci Nabb

51 znaków
50 ściśle i absolutnie niezbędnych znaków + 3 luzaków, którzy wykonali tylko 1
56 przeważnie zbędnych znaków

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

51 rozwiązanie:

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

53 rozwiązanie:

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

Metoda działa na dwóch liniach naraz, jedna zawiera maksymalne sumy osiągnięte w każdym punkcie, a druga zawiera następną linię.

a / 14: Powtórz dwa razy, raz dla każdego wyniku.
8: Weź pierwszą linię z wejścia i przełącz ją za tablicę wejściową, teraz jest to pierwszy zestaw maksymalnych sum.
b / 13: Iteruj po każdej pozostałej linii w tablicy.
9: Wpisz 0 na początku maksymalnych kwot.
c / 12: Iteruj po każdym elemencie linii.
10: Zrób kopię maksymalnych kwot z usuniętym pierwszym elementem.
11: Weź pierwsze 3 elementy maksymalnych sum, posortuj je i dodaj największe do bieżącego elementu linii.

56 rozwiązanie:

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

1: Od wprowadzania do tablicy tablic składających się z 9 znaków, właściwie można to zrobić za pomocą tylko 1, ale złamałem ten klucz, więc trzeba będzie to zrobić.
2: 4 znaki tylko do wykonania transponowanej kopii.
3: Tablica 99 0 na 5 znaków, prawdopodobnie można to zrobić w sposób mądrzejszy, ale palę zbyt dużo trawki, aby wymyślić, jak to zrobić.
4: Zbyt skomplikowana podwójna pętla, która iteruje każdy element wejściowy i robi logikę rozmytą lub coś w tym rodzaju, aby uzyskać wynik. Nabb prawdopodobnie stworzy coś równoważnego u około 3½ znaków.
5: Do tej pory wynik znajduje się wewnątrz tablicy, czyli ten głupiutki fragment kodu jest po prostu, aby go wydostać (i usunąć resztki resztek (i zamienić wynik na miejsce)).
6: To polecenie jest tak proste, że jego liczba znaków prawdopodobnie byłaby ujemna w optymalnym rozwiązaniu. 7: W tym momencie program jest naprawdę gotowy, ale z powodu niechlujstwa w poprzednim kodzie wyjście jest w niewłaściwej kolejności i nie ma spacji, więc tutaj idzie jeszcze kilka bitów.

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)

Odmawiam zrobienia IO, dramatycznie obniżając swój wynik. Przekazuje wszystkie testy w wiązce testowej (chociaż działa to tylko wtedy, gdy wejście kończy się zakończeniem linii, jak w wiązce testowej).

Usunąłem obsługę zakończeń linii Windows, ponieważ Chris zasugerował, że nie jest to konieczne. Wersja wieloplatformowa miałaby a=:".;._2 toJ(1!:1)3jako pierwszą linię.

Wyjaśnienie:

• f daje parę rozwiązania, wywołując p normalnie i transponując dane wejściowe (|: ).
• ppobiera maksimum ( >./) sumy wierszy z zastosowania cmiędzy każdym wierszem (c/ )
• czajmuje dwa rzędy (x i y). Dodaje x do każdego z y, y przesunął w górę o 1 komórkę ( 1|.!.0 y), a y przesunął w dół o 1 komórkę ( _1|.!.0 y). Następnie bierze maksimum z trzech alternatyw dla każdego rzędu. ( >./). Reszta to ranga [sic] - nie jestem pewien, czy robię to dobrze.

Haskell: 314 niezbędnych znaków

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

Uwaga: wymaga to modułu Data.Vector . Nie jestem pewien, czy jest uwzględniony na platformie Haskell, czy nie.

Wersja bez golfa:

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

To rozwiązanie wykorzystuje lenistwo, w połączeniu z Data.Vector , do zapamiętywania. Dla każdego punktu obliczane jest rozwiązanie dla maksymalnej ścieżki od niego do końca, a następnie przechowywane w komórce Vector mi ponownie wykorzystywane w razie potrzeby.

Ruby 1.9, 155 znaków

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]]*" ""

Proste rozwiązanie, które przechodzi wszystkie przypadki testowe.

Haskell, 154 znaków

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

• Edycja: (155 -> 154) wstawiło funkcję złożoną

J, ^{109 + 10 =} 119 znaków

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

Uruchom z tr:

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

Jak zwykle w J, większość kodu dotyczy wejścia / wyjścia. „Rzeczywisty” kod ma 65 znaków:

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

Przechodzi wszystkie przypadki testowe

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)

Gdybym miał obliczyć tylko najkrótszą pionową lub poziomą ścieżkę,
można to zrobić na miejscu, oszczędzając około jednej trzeciej bajtów.

Python, 204 znaki

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)