Estou no ponto (0,0)de um mapa Hx, Wonde a altitude é representada por dígitos, por exemplo:

1132
2221
1230    # H = 3, W = 4

Eu gostaria de experimentar as vistas de todos os picos, que neste caso são as áreas com altitude 3. No entanto, subir montanhas não é uma tarefa fácil, e também estou ficando sem tempo.

Desafio

O desafio é encontrar o caminho mais rápido para visitar todos os picos e voltar.

O programa mais curto vence.

Entrada

• H, W - altura e largura do mapa (Inteiros) (opcional, pode ser uma lista / tupla ou duas entradas inteiras separadas)
• O mapa, fornecido como Hconjuntos de Wdígitos ( 0- 9), em qualquer formato conveniente (lista 2D, sequência separada por novas linhas, etc.)

Saída

• Menor tempo para visitar todos os picos e retornar ao seu ponto de partida (Inteiro)

Condições

• A altitude de uma determinada área é representada por um dígito de 0até 9.
• O "pico" é definido pela área com a maior altitude.
• O caminho deve começar e terminar na área superior esquerda (0,0) .
• Você só pode mover-se para áreas adjacentes à sua área atual e não pode mover-se na diagonal.
  • Leva 3 minutos para mudar de uma área para outra, se não houver mudança de altitude.
  • Demora 11 minutos para subir; isto é, movendo-se de uma área para outra área que é exatamente a 1unidade mais alta.
  • Demora 2 minutos para descer; isto é, movendo-se de uma área para outra área que é exatamente a 1unidade mais baixa.
  • Você não pode mover - se para áreas que são mais do que 1unidades mais altas ou mais baixas do que onde estão. (Você não pode ir de uma área com altitude 1para uma área adjacente com altitude, por exemplo 3)
• Um caminho para todos os picos é garantido
• O número máximo de picos é 15.

Amostras

Entrada

4 5
32445
33434
21153
12343

Saída

96

Explicação

Você começa no canto superior esquerdo 3. Você deve visitar os dois 5s localizados em (0,4)e (3,3)voltar ao 3at (0,0)no menor tempo possível.

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

Saída

75

Mathematica 745 681 bytes

A idéia básica é fazer um gráfico ponderado de possíveis movimentos. Pesos são o tempo que leva para mudar de um lugar para o outro. O caminho com menos peso será o mais rápido.

Os dígitos de entrada são colocados em uma matriz retangular r por c (linhas por colunas) e, em seguida, três representações distintas entram em jogo: (1) um gráfico de grade r por c, em que cada vértice corresponde a uma célula na matriz, (2) (r c) por (r c) matriz de adjacência ponderada que mantém pesos correspondentes ao tempo que leva (2, 3 ou 11 minutos) para mover de um local (no gráfico da grade) para outro e (3) um direcionado , gráfico de adjacência ponderada construído a partir da matriz.

O gráfico de grade ajuda a determinar quais células (ou seja, quais vértices) são possivelmente alcançáveis ​​de cada vértice - "possivelmente alcançáveis" porque uma célula vizinha não deve estar apenas à direita, esquerda, acima ou abaixo de uma determinada célula. Seu valor também deve estar a uma unidade de distância do vizinho (por exemplo, um 3 não se conecta a um vizinho 5 ou 1). Se o vértice anão estiver conectado ao vértice b, as células da matriz de adjacência {a, b} e {b, a} terão o valor ∞. Assim, o gráfico de adjacência ponderada não terá uma aresta de a para b, nem de b para a.

O gráfico de adjacência ponderada serve para determinar a distância mínima ( GraphDistance) e a rota mais curta entre todos os vértices. O caminho ideal deve começar com 1, tocar em cada um dos picos e retornar a 1. Nesse caso, a "rota mais curta" não é necessariamente aquela com menos movimentos. É o que tem o menor tempo total, medido em pesos das arestas.

Golfe

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 mais longa e mais legível

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

Testes

weights["4 5
 32445
 33434
 21153
 12343"]

96

weights@"2 7
 6787778
 5777679"

75

weights@"3 4
 1132
 2221
 1230"

51

Explicação

Pense nas linhas 2-5 da seguinte entrada

"4 5
 32445
 33434
 21153
 12343"

como representando uma matriz com 4 linhas e 5 colunas:

onde cada vértice corresponde a um dígito da matriz de entrada: 3 está no vértice 1, 2 está no vértice 2, 4 está no vértice 3, outro 4 no vértice 4, 5 no vértice 5 etc. O gráfico da grade é apenas aproximado aproximação do gráfico que estamos buscando. Não é direcionado. Além disso, algumas das bordas estarão indisponíveis. (Lembre-se: não podemos passar de uma posição para outra com mais de uma unidade de altura acima ou abaixo da atual.) Mas o gráfico da grade permite encontrar facilmente os vértices que estão próximos a qualquer vértice escolhido. Isso reduz o número de arestas que precisamos considerar, no primeiro exemplo (uma grade de 4 por 5), de 400 (20 * 20) para 62 (31 * 2 é o número de arestas no gráfico de grade). No mesmo exemplo, apenas 48 das arestas estão operacionais; 14 não são.

A seguinte matriz de adjacência ponderada de 20 por 20 representa a distância entre todos os pares de vértices do gráfico de grade.

O código da chave que decide em qual número atribuir está abaixo.

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}->∞}]

A célula {1,2} - na indexação única - contém o valor 2 porque a mudança do vértice 1 para o vértice 2 é descendente. A célula {2,1} contém 11 porque a mudança do vértice 2 para o vértice 1 é subida. Os 3 nas células {1,6} e {6,1} significam que o movimento não é para cima nem para baixo. A célula {1,1} contém ∞ porque não está conectada a si mesma.

O gráfico a seguir mostra a estrutura subjacente à entrada acima. As setas coloridas mostram o caminho ideal do vértice 1 até os picos (em 5 e 14) e voltam para 1. As setas azuis correspondem a movimentos no mesmo nível (3 min); setas vermelhas significam subida (11 min.) e setas verdes indicam descida (2 min).

O caminho do vértice 1 (célula {1,1} para os dois picos e de volta ao vértice 1:

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

96

Pitão, 92 bytes

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

O formato de entrada é um dicionário coordenadas de mapeamento para alturas: {(0, 0): 3, (0, 1): 2, (0, 2): 4, …}. Ele encontra os caminhos mais rápidos entre todos os pares de pontos usando o algoritmo Floyd – Warshall e , em seguida, minimiza o tempo total do ciclo desejado em todas as permutações de picos.

Experimente online