Estoy parado en un punto (0,0)en un mapa Hx Wdonde la altitud está representada por dígitos, por ejemplo:

1132
2221
1230    # H = 3, W = 4

Me gustaría experimentar las vistas desde cada pico, que en este caso son las áreas con altitud 3. Sin embargo, subir colinas no es una tarea fácil, y también me estoy quedando sin tiempo.

Reto

El desafío es encontrar el camino más rápido para visitar todos los picos y volver.

El programa más corto gana.

Entrada

• H, W: altura y ancho del mapa (enteros) (opcional, puede ser una lista / tupla o dos entradas enteras separadas)
• El mapa, dado como Hconjuntos de Wdígitos ( 0- 9), en cualquier formato conveniente (lista 2D, cadena separada por nuevas líneas, etc.)

Salida

• El menor tiempo necesario para visitar cada pico y volver a su punto de partida (Entero)

Condiciones

• La altitud de un área determinada está representada por un dígito de 0a 9.
• El "pico" se define por el área con la altitud más alta.
• La ruta debe comenzar y terminar en el área superior izquierda (0,0) .
• Solo puede moverse a áreas adyacentes a su área actual, y no puede moverse en diagonal.
  • Lleva 3 minutos moverse de un área a otra si no hay cambios en la altitud.
  • Se tarda 11 minutos en subir; es decir, moverse de un área a otra área que es exactamente una 1unidad más alta.
  • Se tarda 2 minutos en bajar; es decir, moverse de un área a otra área que es exactamente la 1unidad más baja.
  • No puede moverse a áreas que sean más de una 1unidad más altas o más bajas que donde se encuentra. (No puede pasar de un área con altitud 1a un área adyacente con altitud, por ejemplo 3)
• Se garantiza un camino a todos los picos.
• El número máximo de picos es 15.

Muestras

Entrada

4 5
32445
33434
21153
12343

Salida

96

Explicación

Empiezas en la esquina superior izquierda 3. Usted tiene que visitar los dos 5s que se encuentran en (0,4)y (3,3)y volver a la 3a (0,0)en el menor tiempo posible.

3  2  4->4->5
V     ^
3->3->4  3  4

2  1  1  5  3

1  2  3  4  3    # 3 + 3 + 11 + 3 + 3 + 11 = 34 minutes to visit 1st peak


3  2  4  4  5
            V
3  3  4  3  4
            V
2  1  1  5  3
         ^  V
1  2  3  4<-3    # 2 + 2 + 3 + 11 + 11 = 29 minutes to visit 2nd


3  2  4  4  5
^            
3  3  4  3  4
^            
2  1  1  5  3
^        V   
1<-2<-3<-4  3    # 2 + 2 + 2 + 2 + 11 + 11 + 3 = 33 minutes to come back

# 34 + 29 + 33 = 96 minutes total is the answer

Entrada

2 7
6787778
5777679

Salida

75

Mathematica 745 681 bytes

La idea básica es hacer una gráfica ponderada de posibles movimientos. Los pesos son el tiempo que lleva moverse de un lugar a otro. El camino con el menor peso será el más rápido.

Los dígitos de entrada se colocan en una matriz rectangular r por c (filas por columnas) y luego entran en juego tres representaciones distintas: (1) una gráfica de cuadrícula r por c, donde cada vértice corresponde a una celda de la matriz, (2) (r c) por (r c) matriz de adyacencia ponderada que contiene los pesos correspondientes al tiempo que lleva (2, 3 u 11 minutos) moverse de una ubicación (en el gráfico de cuadrícula) a otra, y (3) , gráfico de adyacencia ponderado construido a partir de la matriz.

El gráfico de cuadrícula ayuda a determinar qué celdas (es decir, qué vértices) son posiblemente accesibles desde cada vértice, "posiblemente alcanzables" porque una celda vecina no solo debe estar a la derecha, izquierda, arriba o debajo de una celda dada. Su valor también debe estar dentro de 1 unidad de distancia del vecino (por ejemplo, un 3 no se conecta a un vecino 5 o un 1). Si el vértice ano está conectado al vértice b, las celdas de la matriz de adyacencia {a, b} y {b, a} tendrán un valor de ∞. En consecuencia, el gráfico de adyacencia ponderado no tendrá una arista de a a b, ni de b a a.

El gráfico de adyacencia ponderado sirve para determinar la distancia mínima ( GraphDistance) y la ruta más corta entre los vértices. La ruta óptima debe comenzar con 1, tocar cada uno de los picos y volver a 1. En este caso, la "ruta más corta" no es necesariamente la que tiene menos movimientos. Es el que tiene el tiempo total más corto, medido en pesos de borde.

Golfed

o=Sequence;v[a_<->b_,z_]:=(m_~u~q_:={Quotient[m-1,q[[2]]]+1,1+Mod[m-1, q[[2]]]};j=z[[o@@u[a,i=Dimensions@z]]];k=z[[o@@u[b,i]]];Which[j==k,{{a,b}->3,{b,a}->3},j==k-1,{{a,b}->11,{b,a}->2},j==k+1,{{a,b}->2,{b,a}->11},2<4,{{a,b}->∞, {b, a}->∞}]);w@e_:=Module[{d,x,l,y},x=Map[ToExpression,Characters/@Drop[StringSplit@e,2],{2}];d_~l~c_:=d[[2]](c[[1]]-1)+c[[2]];g_~y~p_:=(Min[Plus@@(GraphDistance[g,#,#2]&@@@#)&/@(Partition[#,2,1]&/@({1,o@@#,1}&/@Permutations@p))]);y[WeightedAdjacencyGraph[ReplacePart[ConstantArray[∞,{t=Times@@(d=Dimensions@x),t}],Flatten[#~v~x &/@Union@Flatten[EdgeList[GridGraph@Reverse@d,#<->_]&/@Range@(Times@@d),1],1]]], l[Dimensions@x, #] & /@ Position[x, Max@x]]

Forma más larga y legible

(*determines a weight (number of minutes) to go from vertex a to b and from b to a*)
weight[a_ <-> b_, dat_]:= 
  Module[{cellA,cellB,dim,valA,valB,vertexToCell},

  (*Convert graph vertex index to cell location*)
  vertexToCell[m_,dimen_]:={Quotient[m-1,dim[[2]]]+1,1+Mod[m-1,dimen[[2]]]};
     dim=Dimensions[dat];
     cellA = vertexToCell[a,dim];
     cellB = vertexToCell[b,dim];
     valA=dat[[Sequence@@cellA]];
     valB=dat[[Sequence@@cellB]];
     Which[
       valA==valB,{{a,b}-> 3,{b,a}-> 3},
       valA==valB-1,{{a,b}-> 11,{b,a}-> 2},
       valA==valB+1,{{a,b}-> 2,{b,a}-> 11},
       2<4,{{a,b}->∞,{b,a}->∞}]];

(* weights[] determines the edge weights (times to get from one position to the next), makes a graph and infers the shortest distance 
from vertex 1 to each peak and back.  It tries out all permutations of peaks and 
selects the shortest one. Finally, it returns the length (in minutes) of the shortest trip. *)

weights[str_]:=
  Module[{d,dat,neighbors,cellToVertex,peaks,z,gd},
  dat=Map[ToExpression,Characters/@Drop[StringSplit[str],2],{2}];
  cellToVertex[dim_,cell_]:=dim[[2]] (cell[[1]]-1)+cell[[2]];
  peaks[dat_]:= cellToVertex[Dimensions[dat],#]&/@Position[dat,peak =Max[dat]];

     (* to which cells should each cell be compared? neighbors[] is a function defined within weights[]. It returns a graph, g, from which graph distances will be derived in the function gd[] *)
  neighbors[dim_]:=
  Union@Flatten[EdgeList[GridGraph[Reverse@dim],#<->_]&/@Range@(Times@@dim),1];
    d=Dimensions[dat];
    m=ReplacePart[ConstantArray[∞,{t=Times@@d,t}], 
     (*substitutions=*)
    Flatten[weight[#,dat]&/@neighbors[d],1]];
    g=WeightedAdjacencyGraph[m,VertexLabels->"Name",ImageSize->Full,GraphLayout->"SpringEmbedding"];

    (* finds shortest path.  gd[] is also defined within weights[] *)
  gd[g3_,ps_]:=
    Module[{lists,pairs},
    pairs=Partition[#,2,1]&/@({1,Sequence@@#,1}&/@Permutations@ps);
    Min[Plus@@(GraphDistance[g3,#,#2]&@@@#)&/@pairs]]; 

  gd[g,peaks[dat]]]

Pruebas

weights["4 5
 32445
 33434
 21153
 12343"]

96)

weights@"2 7
 6787778
 5777679"

75)

weights@"3 4
 1132
 2221
 1230"

51)

Explicación

Piense en las líneas 2-5 de la siguiente entrada

"4 5
 32445
 33434
 21153
 12343"

como representando una matriz con 4 filas y 5 columnas:

donde cada vértice corresponde a un dígito de la matriz de entrada: 3 está en el vértice 1, 2 está en el vértice 2, 4 está en el vértice 3, otro 4 en el vértice 4, 5 en el vértice 5, etc. aproximación del gráfico al que apuntamos. No está dirigido Además, algunos de los bordes no estarán disponibles. (Recuerde: no podemos movernos de una posición a otra que esté a más de 1 unidad de altura por encima o por debajo de la actual). Pero el gráfico de cuadrícula nos permite encontrar fácilmente los vértices que están al lado de cualquier vértice elegido. Esto reduce el número de aristas que debemos considerar, en el primer ejemplo (una cuadrícula de 4 por 5), de 400 (20 * 20) a 62 (31 * 2 es el número de aristas en el gráfico de la cuadrícula). En el mismo ejemplo, solo 48 de los bordes están operativos; 14 no lo son.

La siguiente matriz de adyacencia ponderada de 20 por 20 representa la distancia entre todos los pares de vértices desde el gráfico de cuadrícula.

El código clave que decide qué número asignar se encuentra a continuación.

Which[
      valA==valB,{{a,b}-> 3,{b,a}-> 3},
      valA==valB-1,{{a,b}-> 11,{b,a}-> 2},
      valA==valB+1,{{a,b}-> 2,{b,a}-> 11},
      2<4,{{a,b}->∞,{b,a}->∞}]

La celda {1,2}, en una indexación, contiene el valor 2 porque el movimiento desde el vértice 1 al vértice 2 es cuesta abajo. La celda {2,1} contiene 11 porque el movimiento desde el vértice 2 al vértice 1 es cuesta arriba. Los 3 en las celdas {1,6} y {6,1} significan que el movimiento no es ni arriba ni abajo. La celda {1,1} contiene ∞ porque no está conectada a sí misma.

El siguiente gráfico muestra la estructura subyacente a la entrada anterior. Las flechas de colores muestran la ruta óptima desde el vértice 1 hasta los picos (en 5 y 14) y de regreso a 1. Las flechas azules corresponden a movimientos en el mismo nivel (3 min); las flechas rojas significan ascenso (11 min.) y las flechas verdes indican descenso (2 min).

La ruta desde el vértice 1 (celda {1,1} a los dos picos y de regreso al vértice 1:

3 + 3 + 11 + 3 + 3 + 11 + 2 + 2 + 3 + 11 + 11 + 2 + 2 + 2 + 2 + 11 + 11 + 3

96

Pyth, 92 bytes

[email protected],bhS,@Gb+@G,hbH@G,HebG[FQ.dm,(Fb?|tsaMCb>[email protected]@[3hT2)J*QQC.<B+]hSQd1.p.M@Q

El formato de entrada es un diccionario coordenadas de mapeado a alturas: {(0, 0): 3, (0, 1): 2, (0, 2): 4, …}. Esto encuentra las rutas más rápidas entre todos los pares de puntos usando el algoritmo Floyd – Warshall , luego minimiza el tiempo total del ciclo deseado sobre todas las permutaciones de picos.

Pruébalo en línea