Biorąc pod uwagę macierz składającą się z dodatnich liczb całkowitych, wyprowadzaj ścieżkę z najniższą sumą podczas przechodzenia od lewego górnego elementu do prawego dolnego rogu. Możesz poruszać się pionowo, poziomo i po przekątnej. Pamiętaj, że można przesuwać zarówno w górę / w dół, w prawo / w lewo i po przekątnej na wszystkie strony.

Przykład:

 1*   9    7    3   10    2    2
10    4*   1*   1*   1*   7    8
 3    6    3    8    9    5*   7
 8   10    2    5    2    1*   4
 5    1    1    3    6    7    9*

Ścieżka dająca najniższą sumę jest oznaczona gwiazdkami i daje następującą sumę: 1 + 4 + 1 + 1 + 1 + 5 + 1 + 9 = 23 .

Przypadki testowe:

1   1   1
1   1   1
Output: 3

 7    9    6    6    4
 6    5    9    1    6
10    7   10    4    3
 4    2    2    3    7
 9    2    7    9    4
Output: 28

2  42   6   4   1
3  33   1   1   1
4  21   7  59   1
1   7   6  49   1
1   9   2  39   1
Output: 27 (2+3+4+7+7+1+1+1+1)

 5    6    7    4    4
12   12   25   25   25
 9    4   25    9    5
 7    4   25    1   12
 4    4    4    4    4
Output: 34 (5+12+4+4+4+1+4)

1   1   1   1
9   9   9   1
1   9   9   9
1   9   9   9
1   1   1   1
Output: 15

 2   55    5    3    1    1    4    1
 2   56    1   99   99   99   99    5
 3   57    5    2    2    2   99    1
 3   58    4    2    8    1   99    2
 4   65   66   67   68    3   99    3
 2    5    4    3    3    4   99    5
75   76   77   78   79   80   81    2
 5    4    5    1    1    3    3    2
Output: 67 (2+2+3+3+4+5+4+3+3+3+1+2+2+1+3+1+1+4+5+1+2+3+5+2+2)

To jest golf golfowy, więc wygrywa najkrótszy kod w każdym języku.

JavaScript, 442 412 408 358 bajtów

To moje pierwsze zgłoszenie PPCG. Informacje zwrotne będą mile widziane.

(m,h=m.length,w=m[0].length)=>{for(i=0;i<h*w;i++)for(x=0;x<w;x++){for(y=0;y<h;y++){if(m[y][x]%1==0)m[y][x]={c:m[y][x],t:m[y][x]};for(X=-1;X<=1;X++)for(Y=-1;Y<=1;Y++){t=x+X;v=y+Y;if((X==0&&Y==0)||t<0||t>=w||v<0||v>=h)continue;if(m[v][t]%1==0)m[v][t]={c:m[v][t],t:null};c=m[y][x].t+m[v][t].c;if (c<m[v][t].t||m[v][t].t==null)m[v][t].t=c}}}return m[h-1][w-1].t}

To pobiera tablicę wielowymiarową jako dane wejściowe.

Wyjaśnienie

Zasadniczo, przeglądaj wszystkie komórki w kółko, dostosowując najniższy znany koszt, aby dostać się do każdego z sąsiadów. Ostatecznie siatka osiągnie stan, w którym całkowity koszt dotarcia do prawego dolnego rogu jest najniższym kosztem do osiągnięcia.

Próbny

f=(m,h=m.length,w=m[0].length)=>{for(i=0;i<h*w;i++)for(x=0;x<w;x++){for(y=0;y<h;y++){if(m[y][x]%1==0)m[y][x]={c:m[y][x],t:m[y][x]};for(X=-1;X<=1;X++)for(Y=-1;Y<=1;Y++){t=x+X;v=y+Y;if((X==0&&Y==0)||t<0||t>=w||v<0||v>=h)continue;if(m[v][t]%1==0)m[v][t]={c:m[v][t],t:null};c=m[y][x].t+m[v][t].c;if (c<m[v][t].t||m[v][t].t==null)m[v][t].t=c}}}return m[h-1][w-1].t}

//Tests
console.log(f([[1,1,1],[1,1,1]])===3);
console.log(f([[7,9,6,6,4],[6,5,9,1,6],[10,7,10,4,3],[4,2,2,3,7],[9,2,7,9,4]])===28);
console.log(f([[2,42,6,4,1],[3,33,1,1,1],[4,21,7,59,1],[1,7,6,49,1],[1,9,2,39,1]])===27);
console.log(f([[5,6,7,4,4],[12,12,25,25,25],[9,4,25,9,5],[7,4,25,1,12],[4,4,4,4,4]])===34); 
console.log(f([[1,1,1,1],[9,9,9,1],[1,9,9,9],[1,9,9,9],[1,1,1,1]])===15)
console.log(f([[2,55,5,3,1,1,4,1],[2,56,1,99,99,99,99,5],[3,57,5,2,2,2,99,1],[3,58,4,2,8,1,99,2],[4,65,66,67,68,3,99,3],[2,5,4,3,3,4,99,5],[75,76,77,78,79,80,81,2],[5,4,5,1,1,3,3,2]])===67);

Edycja: Specjalne podziękowania dla @ETHproductions za pomoc w goleniu dziesiątek smacznych bajtów.

Więcej dzięki @Stewie Griffin za wskazówki, które przewróciły 50 bajtów.

Python 3 + numpy + scipy , 239 222 186 bajtów

from numpy import*
from scipy.sparse.csgraph import*
def f(M):m,n=s=M.shape;x,y=indices(s);return dijkstra([(M*(abs(i//n-x)<2)*(abs(i%n-y)<2)).flatten()for i in range(m*n)])[0,-1]+M[0,0]

Wypróbuj online!

Pakiet Octave + Image Processing, 175 162 157 151 142 139 139 bajtów

Zaoszczędzono 14 bajtów dzięki @Luis Mendo i 1 bajt dzięki @notjagan

function P(G)A=inf(z=size(G));A(1)=G(1);for k=G(:)'B=im2col(padarray(A,[1,1],inf),[3,3])+G(:)';B(5,:)-=G(:)';A=reshape(min(B),z);end,A(end)

Korzysta z pakietu przetwarzania obrazu, ponieważ dlaczego nie? Czy to nie tak wszyscy rozwiązują problemy z grafem?

Wypróbuj online!

Eksplodował

function P(G)
   A=inf(z=size(G));         % Initialize distance array to all Inf
   A(1)=G(1);                % Make A(1) = cost of start cell
   for k=G(:)'               % For a really long time...
      B=im2col(padarray(A,[1,1],inf),[3,3])+G(:)';
       %  B=padarray(A,[1,1],inf);     % Add border of Inf around distance array
       %  B=im2col(B,[3,3]);           % Turn each 3x3 neighborhood into a column
       %  B=B+G(:)';                   % Add the weights to each row
      B(5,:)-=G(:)';         % Subtract the weights from center of neighborhood
      A=reshape(min(B),z);   % Take minimum columnwise and reshape to original
   end
   A(end)                    % Display cost of getting to last cell

Wyjaśnienie

Biorąc pod uwagę tablicę wag:

7   12    6    2    4
5   13    3   11    1
4    7    2    9    3
4    2   12   13    4
9    2    7    9    4

Zainicjuj tablicę kosztów, aby koszt dotarcia do każdego elementu wynosił Nieskończoność, z wyjątkiem punktu początkowego (lewy górny element), którego koszt jest równy jego wadze.

  7   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf

Jest to iteracja 0. Dla każdej kolejnej iteracji koszt dotarcia do komórki jest ustawiony na minimum:

• aktualny koszt osiągnięcia tego elementu, oraz
• aktualny koszt dotarcia do sąsiadów elementu + waga elementu

Po pierwszej iteracji koszt ścieżki do elementu (2,2) (przy użyciu indeksowania 1) wyniesie

minimum([  7   Inf   Inf]   [13  13  13]) = 20
        [Inf   Inf   Inf] + [13   0  13]
        [Inf   Inf   Inf]   [13  13  13]

Pełna tablica kosztów po pierwszej iteracji wyglądałaby następująco:

  7    19   Inf   Inf   Inf
 12    20   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf

Po iteracji kkażdy element będzie najniższym kosztem dotarcia do tego elementu od samego początku, wykonując co najmniej kkilka kroków. Na przykład element w (3,3) można osiągnąć w 2 krokach (iteracjach) za koszt 22:

  7    19    25   Inf   Inf
 12    20    22   Inf   Inf
 16    19    22   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf

Ale podczas czwartej iteracji znajduje się ścieżka 4 kroków o koszcie 20:

 7   19   25   24   28
12   20   22   32   25
16   19   20   30   34
20   18   30   34   35
27   20   25   40   39

Ponieważ żadna ścieżka przez macierz MXN nie może być dłuższa niż liczba elementów w macierzy (jako bardzo luźna górna granica), po m*niteracjach każdy element będzie zawierał koszt najkrótszej ścieżki, aby dotrzeć do tego elementu od samego początku.

JavaScript, 197 bajtów

a=>(v=a.map(x=>x.map(_=>1/0)),v[0][0]=a[0][0],q=[...(a+'')].map(_=>v=v.map((l,y)=>l.map((c,x)=>Math.min(c,...[...'012345678'].map(c=>a[y][x]+((v[y+(c/3|0)-1]||[])[x+c%3-1]||1/0)))))),v.pop().pop())

Upiększać:

a=>(
  // v is a matrix holds minimal distance to the left top
  v=a.map(x=>x.map(_=>1/0)),
  v[0][0]=a[0][0],
  q=[
     // iterate more than width * height times to ensure the answer is correct
    ...(a+'')
  ].map(_=>
    v=v.map((l,y)=>
      l.map((c,x)=>
        // update each cell
        Math.min(c,...[...'012345678'].map(
          c=>a[y][x]+((v[y+(c/3|0)-1]||[])[x+c%3-1]||1/0)
        ))
      )
    )
  ),
  // get result at right bottom
  v.pop().pop()
)

Mathematica 279 bajtów

Podstawową ideą jest stworzenie wykresu z wierzchołkami odpowiadającymi wpisom macierzy i skierowanymi krawędziami między dowolnymi dwoma wierzchołkami oddzielonymi od siebie ChessboardDistancewiększą niż zero, ale mniejszą lub równą 1. Nawiasem mówiąc, tak się składa, że ​​jest znany jako wykres Kinga , ponieważ odpowiada ważne ruchy króla na szachownicy.

FindShortestPathjest następnie używany do uzyskania minimalnej ścieżki. Działa EdgeWeight, nie VertexWeight, więc istnieje dodatkowy kod do zdefiniowania EdgeWeightjako wpis macierzy odpowiadający celowi każdej ukierunkowanej krawędzi.

Kod:

(m=Flatten[#];d=Dimensions@#;s=Range[Times@@d];e=Select[Tuples[s,2],0<ChessboardDistance@@(#/.Thread[s->({Ceiling[#/d[[1]]],Mod[#,d[[1]],1]}&/@s)])≤1&];Tr[FindShortestPath[Graph[s,#[[1]]->#[[2]]&/@e,EdgeWeight->(Last@#&/@Map[Extract[m,#]&,e,{2}])],1,Last@s]/.Thread[s->m]])&

Zauważ, że znak jest symbolem transpozycji. Wklei się w Mathematica bez zmian.

Stosowanie:

%@{{2, 55, 5, 3, 1, 1, 4, 1},
  {2, 56, 1, 99, 99, 99, 99, 5},
  {3, 57, 5, 2, 2, 2, 99, 1},
  {3, 58, 4, 2, 8, 1, 99, 2},
  {4, 65, 66, 67, 68, 3, 99, 3},
  {2, 5, 4, 3, 3, 4, 99, 5},
  {75, 76, 77, 78, 79, 80, 81, 2},
  {5, 4, 5, 1, 1, 3, 3, 2}}

Wynik:

67

Jeśli ustawisz, g=Graph[...,GraphLayout->{"GridEmbedding","Dimension"->d},VertexLabels->Thread[s->m]a p=FindShortestPath[...następnie poniższa grafika wyświetli rozwiązanie (górna część matrycy odpowiada dolnej części wykresu):

HighlightGraph[g,PathGraph[p,Thread[Most@p->Rest@p]]]

Haskell, 228 bajtów

Pozycje są listami dwóch elementów, ponieważ są one łatwe do wygenerowania sequencei tak samo łatwe do dopasowania, jak 2-krotki.

h=g[[-1,-1]]
g t@(p:r)c|p==m=0|1<2=minimum$(sum$concat c):(\q@[a,b]->c!!a!!b+g(q:t)c)#(f(e$s$(\x->[0..x])#m)$f(not.e t)$zipWith(+)p#s[[-1..1],[-1..1]])where m=[l(c)-1,l(head c)-1]
(#)=map
f=filter
e=flip elem
s=sequence
l=length

Zacznij od -1,-1i policz koszt każdego pola docelowego kroków.

Alternatywne dwa pierwsze wiersze: zacznij o 0,0, policz pola wyjściowe, zakończ współrzędnymi równymi wymiarom macierzy (czyli w prawo od celu, który należy dodać do listy legalnych miejsc docelowych) - dokładnie tej samej długości, ale wolniej:

j=i[[0,0]]
i t@(p@[a,b]:r)c|p==m=0|1<2=c!!a!!b+(minimum$(sum$concat c):(\q->i(q:t)c)#(f(e$m:(s$(\x->[0..x-1])#m))$f(not.e t)$zipWith(+)p#s[[-1..1],[-1..1]]))where m=[l c,l$head c]

Użycie przyrostka dla mapnie oszczędza tutaj bajtów, ale zastępuję go, gdy tylko nie kosztuje, ponieważ może być lepszy tylko przy większej liczbie zastosowań, a czasem także przy innych restrukturyzacjach, które golą kolejną parę nawiasów.

Do poprawy: Redundantne filters. Scalanie / w-podszewka je filter(flip elem$(s$(\x->[0..x])#m)\\p)z import Data.Listna \\koszty 3 bajtów.

Również szkoda, że (fromEnumTo 0)2 bajty są dłuższe niż (\x->[0..x]).

sum$concat cjest sumą kosztu wszystkich pól, a tym samym zwięźle wyrażoną górną granicą kosztu ścieżki, która jest podawana, aby minimumuniknąć pustej listy (mój moduł sprawdzania typu już ustalił całą rzecz do pracy na Integers, więc nie zakoduj na stałe maksimum , hehe). Bez względu na to, w jaki sposób ograniczam kroki w oparciu o poprzednio wykonane (co znacznie przyspieszyłoby algorytm, ale także koszt bajtów), nie mogę uniknąć ślepych zaułków, które sprawiają, że ten powrót jest konieczny.

• Jednym z pomysłów na filtrowanie było ((not.e n).zipWith(-)(head r))wyodrębnienie n=s[[-1..1],[-1..1]], które wymaga dodania ,[-1,-1]do początkowej ścieżki. Algorytm unika następnie przejścia tam, gdzie mógł już być w poprzednim kroku, co sprawia, że ​​stąpanie po polu krawędzi prostopadle do tej krawędzi jest ślepym zaułkiem.

• Innym było ((>=0).sum.z(*)d)wyodrębnienie z=zipWith, które wprowadza nowy argument ddo funkcji rekurencyjnej, który jest podany tak jak (z(-)p q)w rekurencji i [1,1]w pierwszym przypadku. Algorytm unika kolejnych kroków z ujemnym iloczynem skalarnym ( dbędącym poprzednim krokiem), co oznacza brak ostrych obrotów o 45 °. To wciąż znacznie zawęża możliwości i pozwala uniknąć trywialnego ślepego zaułka, ale wciąż istnieją ścieżki, które kończą się w już odwiedzonych polach (i być może „ucieczka”, która byłaby jednak ostrym zakrętem).

Python 2, 356 320 bajtów

s=input()
r=lambda x:[x-1,x,x+1][-x-2:]
w=lambda z:[z+[(x,y)]for x in r(z[-1][0])for y in r(z[-1][1])if x<len(s)>0==((x,y)in z)<len(s[0])>y]
l=len(s)-1,len(s[0])-1
f=lambda x:all(l in y for y in x)and x or f([a for b in[l in z and[z]or w(z)for z in x]for a in b])
print min(sum(s[a][b]for(a,b)in x)for x in f([[(0,0)]]))

Wypróbuj tutaj!

-36 bajtów dzięki notjagan !

Pobiera listę list jako dane wejściowe i generuje najniższy koszt podczas nawigacji po matrycy od lewego górnego rogu do prawego dolnego rogu.

Wyjaśnienie

Znajdź każdą możliwą trasę od lewego górnego do prawego dolnego rogu macierzy, tworząc listę współrzędnych x, y dla każdej trasy. Trasy nie mogą się wycofać i muszą kończyć się na (len(s)-1,len(s[0])-1).

Zsumuj liczby całkowite na każdej ścieżce współrzędnych i zwróć minimalny koszt.

printMożna łatwo zmienić na wyjście wykaz współrzędnych na najkrótszej trasie.

APL (Dyalog Classic) , 33 bajty

{⊃⌽,(⊢⌊⍵+(⍉3⌊/⊣/,⊢,⊢/)⍣2)⍣≡+\+⍀⍵}

Wypróbuj online!

{ } funkcja z argumentem ⍵

+\+⍀⍵ weź częściowe sumy według wiersza i kolumny, aby ustalić pesymistyczną górną granicę odległości ścieżek

( )⍣≡ powtarzaj aż do konwergencji:

• (⍉3⌊/⊣/,⊢,⊢/)⍣2 min odległości do sąsiadów, tj. zrobić dwa razy (( )⍣2 ): dodaj do lewej kolumny ( ⊣/,) do self ( ⊢) i dołącz kolumny z prawej strony ( ,⊢/), znajdź minima w poziomych trójkach ( 3⌊/) i transponuj ( ⍉)

• ⍵+ dodaj wartość każdego węzła do jego minimalnych odległości do sąsiadów

• ⊢⌊ staraj się pokonać aktualne najlepsze odległości

⊃⌽, na koniec zwróć prawą dolną komórkę