Ruta óptima a través de una matriz.

19

Dada una matriz que consiste en enteros positivos, genera la ruta con la suma más baja cuando se atraviesa desde el elemento superior izquierdo hasta el inferior derecho. Puede moverse verticalmente, horizontalmente y diagonalmente. Tenga en cuenta que es posible moverse hacia arriba / abajo, derecha / izquierda y diagonalmente a todos los lados.

Ejemplo:

 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*

La ruta que da la suma más baja está marcada con asteriscos y da como resultado la siguiente suma: 1 + 4 + 1 + 1 + 1 + 5 + 1 + 9 = 23 .

Casos de prueba:

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)

Este es el por lo que gana el código más corto en cada idioma.

Stewie Griffin
fuente
Muy similar , aunque no permite el movimiento diagonal.
Mego
77
@WheatWizard no estoy de acuerdo. Además de las diferencias en su mayoría superficiales de que este desafío permite el movimiento diagonal y todas las posiciones son accesibles, el otro desafío requiere el retorno del camino en lugar de solo el costo del camino. A menos que esté utilizando incorporados que devuelvan ambos, el código no es intercambiable.
vaso de precipitados
@beaker Realmente no veo la diferencia. Tienes que encontrar el camino para saber su longitud. La diferencia aquí es una diferencia bastante pequeña en la producción en mi opinión y este desafío no ofrece nada nuevo o interesante que no esté cubierto por ese desafío.
Wheat Wizard
1
@WheatWizard Mi solución aquí no encuentra la ruta. Se podría encontrar el camino, pero no sin una matriz predecesor separada y la lógica para evitar hacer un nodo de su propio predecesor. Sin mencionar la recuperación del camino al final.
vaso de precipitados
@beaker La modificación es bastante trivial en mi opinión. Independientemente de que la cuestión de los engañados no sea si cada entrada válida en un desafío puede ser transferida con un mínimo esfuerzo, se trata del caso general. No solo creo que la mayoría de los esfuerzos aquí pueden ser portados, no creo que este desafío ofrezca algo nuevo o interesante del otro.
Wheat Wizard

Respuestas:

8

JavaScript, 442 412 408 358 bytes

Esta es mi primera presentación PPCG. Se agradecería cualquier comentario.

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

Esto toma una matriz multidimensional como entrada.

Explicación

Básicamente, recorra todas las celdas una y otra vez ajustando el costo más bajo conocido para llegar a cada uno de los vecinos. Finalmente, la cuadrícula alcanzará un estado donde el costo total para llegar a la esquina inferior derecha es el costo más bajo para llegar allí.

Manifestación

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

Editar: Un agradecimiento especial a @ETHproductions por ayudarme a afeitar docenas de sabrosos bytes.

Más gracias a @Stewie Griffin por sus consejos que eliminaron 50 bytes.

Benjamin Cuningham
fuente
3
Bienvenido a PPCG! Hay algunos espacios adicionales que podría eliminar hacia el final (cuento un total de 5), y no necesita ninguno de los puntos y comas directamente antes de lo }cual debería ahorrar algunos bytes. Tampoco necesita declarar sus variables; Creo que eliminar los vars debería ahorrarte 24 bytes más en total.
ETHproductions
2
Bienvenido a PPCG =) Me alegra que hayas elegido uno de mis desafíos como punto de partida. Mi único comentario: me encantan las explicaciones. Sin embargo, es opcional, por lo que no tiene que agregarlo a menos que lo desee. :)
Stewie Griffin
Creo que tal vez el almacenamiento m[v][t]como una variable: t=x+X;v=y+Y;k=m[v][t]¿será aún más corto ...?
Stewie Griffin
7

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]

Pruébalo en línea!

notjagan
fuente
6

Octave + Paquete de procesamiento de imágenes, 175 162 157 151 142 139 bytes

Ahorró 14 bytes gracias a @Luis Mendo y 1 byte gracias a @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)

Utiliza el paquete de procesamiento de imágenes, porque ¿por qué no? ¿No es así como todos resuelven los problemas gráficos?

Pruébalo en línea!

Explotó

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

Explicación

Dada una variedad de pesos:

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

Inicialice una matriz de costos para que el costo de alcanzar cada elemento sea Infinito, excepto el punto de partida (el elemento superior izquierdo) cuyo costo es igual a su peso.

  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

Esta es la iteración 0. Para cada iteración posterior, el costo para llegar a una celda se establece en el mínimo de:

  • el costo actual para alcanzar ese elemento, y
  • el costo actual para llegar a los vecinos del elemento + el peso del elemento

Después de la primera iteración, el costo de la ruta al elemento (2,2) (usando indexación basada en 1) será

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

La matriz de costos completa después de la primera iteración sería:

  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

Después de la iteración k, cada elemento será el costo más bajo de llegar a ese elemento desde el principio siguiendo la mayoría de los kpasos. Por ejemplo, el elemento en (3,3) se puede alcanzar en 2 pasos (iteraciones) por un costo de 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

Pero en la cuarta iteración, se encuentra una ruta de 4 pasos con un costo de 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

Dado que ninguna ruta a través de la matriz mxn puede ser más larga que el número de elementos en la matriz (como un límite superior muy suelto), después de las m*niteraciones, cada elemento contendrá el costo de la ruta más corta para llegar a ese elemento desde el principio.

cubilete
fuente
-1 byte eliminando el espacio entre whiley ~.
notjagan
@notjagan Cambié de whilea fory todavía era capaz de utilizar su punta. ¡Gracias!
vaso de precipitados
5

JavaScript, 197 bytes

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

Embellecer:

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()
)
tsh
fuente
4

Mathematica 279 Bytes

La idea básica es crear un gráfico con vértices correspondientes a entradas de matriz y aristas dirigidas entre dos vértices separados por un valor ChessboardDistancemayor que cero pero menor o igual que 1. Por cierto, esto se conoce como un gráfico King , ya que corresponde a Los movimientos válidos de un rey en un tablero de ajedrez.

FindShortestPathluego se usa para obtener la ruta mínima. Funciona EdgeWeight, no VertexWeight, por lo que hay un código adicional para definir EdgeWeightcomo la entrada de matriz correspondiente al destino de cada borde dirigido.

Código:

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

Tenga en cuenta que el carácter es el símbolo de transposición. Se pegará en Mathematica tal cual.

Uso:

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

Salida:

67

Si configura g=Graph[...,GraphLayout->{"GridEmbedding","Dimension"->d},VertexLabels->Thread[s->m]y p=FindShortestPath[...luego el siguiente gráfico mostrará visualmente la solución (la parte superior de la matriz corresponde a la parte inferior del gráfico):

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

ingrese la descripción de la imagen aquí

Kelly Lowder
fuente
3

Haskell, 228 bytes

Las posiciones son listas de dos elementos, porque son fáciles de generar sequencee igual de fáciles de combinar que las 2 tuplas.

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

Comience -1,-1y cuente el costo del campo de destino de cada paso.

Primeras dos líneas alternativas: comience en 0,0, cuente los campos de salida, termine en las coordenadas iguales a las dimensiones de la matriz (tan hacia abajo a la derecha del objetivo, que debe agregarse a la lista de destinos legales), exactamente la misma longitud pero más lenta:

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]

El uso de un infijo para mapno ahorra bytes aquí, pero lo sustituyo tan pronto como no cuesta uno, porque solo puede mejorar con más usos y, a veces, también con otras reestructuraciones que eliminan otro par de paréntesis.

Para mejorar: redundante filters. La fusión de / en-alineándolos a filter(flip elem$(s$(\x->[0..x])#m)\\p)la import Data.Listde \\los costos de 3 bytes.

Además, muy mal (fromEnumTo 0)es 2 bytes más largo que (\x->[0..x]).

sum$concat ces el costo de todos los campos resumido y, por lo tanto, un límite superior expresable de manera concisa en el costo de la ruta que se le da para minimumevitar una lista vacía (mi comprobador de tipos ya ha determinado todo para trabajar en Integers, por lo que no hay que codificar el máximo , jeje). No importa cómo restrinja los pasos basados ​​en el anterior realizado (lo que aceleraría mucho el algoritmo, pero también costaría bytes), no puedo evitar los callejones sin salida que hacen necesario este retroceso.

  • Una idea de filtro fue la ((not.e n).zipWith(-)(head r))extracción n=s[[-1..1],[-1..1]], que requiere agregar ,[-1,-1]a la ruta inicial. El algoritmo evita ir a donde ya podría haber ido en el paso anterior, lo que hace que pisar un campo de borde ortogonalmente a ese borde sea un callejón sin salida.

  • Otro fue ((>=0).sum.z(*)d)con la extracción z=zipWith, que introduce un nuevo argumento dpara la función recursiva que se da como (z(-)p q)en la recursividad y [1,1]en el caso inicial. El algoritmo evita pasos sucesivos con un producto escalar negativo (que des el paso anterior), lo que significa que no hay vueltas bruscas de 45 °. Esto todavía reduce considerablemente las opciones y evita el callejón sin salida trivial anterior, pero todavía hay caminos que terminan encerrados en campos ya visitados (y posiblemente un 'escape' que, sin embargo, sería un giro brusco).

Leif Willerts
fuente
3

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

Pruébalo aquí!

-36 bytes gracias a notjagan !

Recibe una lista de listas como entrada y genera el costo más bajo cuando navega por la matriz desde la parte superior izquierda a la parte inferior derecha.

Explicación

Encuentre todas las rutas posibles desde la parte superior izquierda hasta la parte inferior derecha de la matriz, creando una lista de coordenadas x, y para cada ruta. Las rutas no pueden dar marcha atrás, y deben terminar en (len(s)-1,len(s[0])-1).

Suma los enteros en cada ruta de coordenadas y devuelve el costo mínimo.

Se printpuede cambiar fácilmente para generar la lista de coordenadas para la ruta más corta.

Solvacion
fuente
-36 bytes con algunos cambios misceláneos.
notjagan
@notjagan Grandes cambios, especialmente el uso de orlos condicionales. ¡Gracias!
Solvación
1

APL (Dyalog Classic) , 33 bytes

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

Pruébalo en línea!

{ } funcionar con argumento

+\+⍀⍵ tomar sumas parciales por fila y por columna para establecer un límite superior pesimista en las distancias de ruta

( )⍣≡ repetir hasta la convergencia:

  • (⍉3⌊/⊣/,⊢,⊢/)⍣2min de distancias a los vecinos, es decir, hacer dos veces ( ( )⍣2): anteponer la columna más a la izquierda ( ⊣/,) a self ( ) y agregar las columnas más a la derecha ( ,⊢/), encontrar los mínimos en triples horizontales ( 3⌊/) y transponer ( )

  • ⍵+ agregue el valor de cada nodo a su mínimo de distancias a los vecinos

  • ⊢⌊ intenta superar las mejores distancias actuales

⊃⌽, finalmente, devuelve la celda inferior derecha

ngn
fuente