Geben Sie bei einer Matrix aus positiven Ganzzahlen den Pfad mit der niedrigsten Summe aus, wenn Sie vom linken oberen Element zum rechten unteren Element wechseln. Sie können sich vertikal, horizontal und diagonal bewegen. Beachten Sie, dass es möglich ist, sich nach oben / unten, rechts / links und diagonal nach allen Seiten zu bewegen.

Beispiel:

 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*

Der Pfad mit der niedrigsten Summe ist mit Sternchen markiert und ergibt die folgende Summe: 1 + 4 + 1 + 1 + 1 + 5 + 1 + 9 = 23 .

Testfälle:

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)

Das ist Code-Golf, also gewinnt der kürzeste Code in jeder Sprache.

JavaScript, 442 412 408 358 Bytes

Dies ist meine erste PPCG-Einreichung. Rückmeldungen sind erwünscht.

(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}

Dies nimmt ein mehrdimensionales Array als Eingabe.

Erläuterung

Grundsätzlich sollten Sie alle Zellen immer wieder durchlaufen und die niedrigsten bekannten Kosten anpassen, um zu jedem der Nachbarn zu gelangen. Irgendwann erreicht das Gitter einen Zustand, in dem die Gesamtkosten für das Erreichen der unteren rechten Ecke die niedrigsten Kosten sind.

Demo

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);

Edit: Besonderer Dank geht an @ETHproductions, die mir geholfen haben, Dutzende leckerer Bytes zu rasieren.

Vielen Dank an @Stewie Griffin für Ihre Tipps, die 50 Bytes gekostet haben .

Python 3 + numpy + scipy , 239 222 186 Bytes

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]

Probieren Sie es online!

Octave + Bildverarbeitungspaket, 175 162 157 151 142 139 Bytes

Dank @Luis Mendo 14 Byte und dank @notjagan 1 Byte gespeichert

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)

Verwendet das Bildverarbeitungspaket, warum nicht? Lösen nicht alle so Grafikprobleme?

Probieren Sie es online!

Explodiert

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

Erläuterung

Eine Reihe von Gewichten gegeben:

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

Initialisieren Sie ein Kostenarray so, dass die Kosten für das Erreichen jedes Elements unendlich sind, mit Ausnahme des Startpunkts (oberes linkes Element), dessen Kosten gleich seinem Gewicht sind.

  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

Dies ist Iteration 0. Für jede nachfolgende Iteration werden die Kosten zum Erreichen einer Zelle auf das Minimum von festgelegt:

• die aktuellen Kosten, um dieses Element zu erreichen, und
• Die aktuellen Kosten, um die Nachbarn des Elements zu erreichen, + das Gewicht des Elements

Nach der ersten Iteration betragen die Kosten für den Pfad zum Element (2,2) (unter Verwendung einer 1-basierten Indizierung)

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

Das vollständige Kostenarray nach der ersten Iteration wäre:

  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

Nach der Iteration kstellt jedes Element die niedrigsten Kosten für das Erreichen dieses Elements von Anfang an dar, wobei höchstens kSchritte unternommen werden. Zum Beispiel kann das Element bei (3,3) in 2 Schritten (Iterationen) zu einem Preis von 22 erreicht werden:

  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

Bei der 4. Iteration wird jedoch ein Pfad mit 4 Schritten mit Kosten von 20 gefunden:

 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

Da kein Pfad durch die mxn- Matrix länger sein kann als die Anzahl der Elemente in der Matrix (als sehr lockere Obergrenze), enthält m*njedes Element nach Iterationen die Kosten des kürzesten Pfades, um dieses Element von Anfang an zu erreichen.

JavaScript, 197 Byte

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())

Verschönern Sie:

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 Bytes

Grundidee ist einen Graph mit den Eckpunkten entsprechend Matrixeinträge und gerichtete Kanten zwischen zwei beliebigen Vertices von einer getrennt zu schaffen ChessboardDistancegrößer als Null aber kleiner als oder gleich 1. Im übrigen geschieht dies als bekannt seinen König Graph , da sie entspricht die gültigen Züge eines Königs auf einem Schachbrett.

FindShortestPathwird dann verwendet, um den minimalen Pfad zu erhalten. Funktioniert EdgeWeightnicht VertexWeight, daher gibt es einen zusätzlichen Code, um den EdgeWeightals Matrixeintrag zu definieren, der dem Ziel jeder gerichteten Kante entspricht.

Code:

(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]])&

Beachten Sie, dass das Zeichen das Transponierungssymbol ist. Es wird unverändert in Mathematica eingefügt.

Verwendung:

%@{{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}}

Ausgabe:

67

Wenn Sie g=Graph[...,GraphLayout->{"GridEmbedding","Dimension"->d},VertexLabels->Thread[s->m]und p=FindShortestPath[...dann festlegen, zeigt die folgende Grafik die Lösung visuell an (der obere Rand der Matrix entspricht dem unteren Rand der Grafik):

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

Haskell, 228 Bytes

Positionen sind Listen mit zwei Elementen, da diese einfach zu generieren sequenceund genauso einfach zu kopieren sind wie 2-Tupel.

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

Beginnen Sie mit -1,-1und zählen Sie die Kosten für jedes Schrittzielfeld.

Alternative erste beiden Zeilen: Beginnen Sie mit 0,0, zählen Sie die Abflugfelder und enden Sie an den Koordinaten, die den Matrixabmessungen entsprechen (also rechts unten vom Ziel, das zur Liste der zulässigen Ziele hinzugefügt werden muss) - exakt dieselbe Länge, aber langsamer:

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]

Das Verwenden eines Infixes für mapspart hier keine Bytes, aber ich ersetze es, sobald es keinen kostet, weil es nur mit mehr Verwendungen und manchmal auch mit anderen Umstrukturierungen besser werden kann, die ein anderes Klammerpaar abschneiden.

Zu verbessern: Redundante filters. Merging / in-Futter sie filter(flip elem$(s$(\x->[0..x])#m)\\p)mit import Data.Listfür \\Kosten 3 Bytes.

Auch zu schade, (fromEnumTo 0)ist 2 Bytes länger als (\x->[0..x]).

sum$concat cwerden die Kosten aller Felder aufsummiert und damit eine präzise ausdrückbare Obergrenze für die Pfadkosten angegeben, minimumum eine leere Liste zu vermeiden (meine Typprüfung hat bereits festgelegt, woran alles gearbeitet werden soll Integer, also kein hartes Kodieren des Maximums) hehe). Egal, wie ich Schritte einschränke, die auf den vorherigen Schritten basieren (was den Algorithmus erheblich beschleunigen würde, aber auch Byte kosten würde), ich kann die Sackgassen nicht vermeiden, die dieses Zurückfallen erforderlich machen.

• Eine Filteridee war das ((not.e n).zipWith(-)(head r))Extrahieren n=s[[-1..1],[-1..1]], was das Hinzufügen ,[-1,-1]zum Anfangspfad erfordert . Der Algorithmus vermeidet dann, dorthin zu gehen, wo er bereits im vorherigen Schritt hätte sein können, wodurch das orthogonale Betreten eines Kantenfelds zu einer Sackgasse wird.

• Eine andere war das ((>=0).sum.z(*)d)Extrahieren z=zipWith, das dder rekursiven Funktion, die wie (z(-)p q)in der Rekursion und [1,1]im Anfangsfall angegeben ist, ein neues Argument hinzufügt . Der Algorithmus vermeidet aufeinanderfolgende Schritte mit einem negativen Skalarprodukt ( ddas der vorherige Schritt ist), was bedeutet, dass keine scharfen 45 ° -Drehungen auftreten. Dies schränkt die Auswahlmöglichkeiten immer noch erheblich ein und vermeidet die vorherige triviale Sackgasse, aber es gibt immer noch Wege, die in bereits besuchten Feldern eingeschlossen sind (und möglicherweise eine „Flucht“, die jedoch eine scharfe Wendung darstellen würde).

Python 2, 356 320 Bytes

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)]]))

Probieren Sie es hier aus!

-36 bytes dank notjagan !

Erhält eine Liste mit Listen als Eingabe und gibt die niedrigsten Kosten aus, wenn Sie in der Matrix von links oben nach rechts unten navigieren.

Erläuterung

Suchen Sie jede mögliche Route von links oben nach rechts unten in der Matrix, und erstellen Sie für jede Route eine Liste mit x- und y-Koordinaten. Die Routen können nicht zurückverfolgt werden und müssen bei enden (len(s)-1,len(s[0])-1).

Summieren Sie die Ganzzahlen auf jedem Koordinatenpfad und geben Sie die minimalen Kosten zurück.

Das printkann leicht geändert werden, um die Liste der Koordinaten für die kürzeste Route auszugeben.

APL (Dyalog Classic) , 33 Byte

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

Probieren Sie es online!

{ } Funktion mit Argument ⍵

+\+⍀⍵ Nehmen Sie Teilsummen pro Zeile und pro Spalte, um eine pessimistische Obergrenze für Pfadentfernungen festzulegen

( )⍣≡ wiederhole bis zur Konvergenz:

• (⍉3⌊/⊣/,⊢,⊢/)⍣2Minimale Abstände zu Nachbarn, dh zweimal ( ( )⍣2): linke Spalte ( ⊣/,) vor sich selbst ( ⊢) stellen und rechte Spalte ( ) anhängen ,⊢/, Minima in horizontalen Tripeln finden ( 3⌊/) und transponieren ( ⍉)

• ⍵+ Addieren Sie den Wert jedes Knotens zu den Mindestentfernungen zu den Nachbarn

• ⊢⌊ versuche die aktuell besten Distanzen zu schlagen

⊃⌽, Geben Sie zum Schluss die untere rechte Zelle zurück