Stoję w punkcie (0,0)na mapie Hx, Wgdzie wysokość jest reprezentowana przez cyfry, na przykład:

1132
2221
1230    # H = 3, W = 4

Chciałbym doświadczyć widoków z każdego szczytu, którym w tym przypadku są obszary o wysokości 3. Jednak wspinanie się na wzgórza nie jest łatwym zadaniem, a ja również brakuje mi czasu.

Wyzwanie

Wyzwanie polega na znalezieniu najszybszej ścieżki do odwiedzenia wszystkich szczytów i powrotu.

Najkrótszy program wygrywa.

Wkład

• H, W - wysokość i szerokość mapy (liczby całkowite) (opcjonalnie, może to być lista / krotka lub dwa oddzielne wejścia całkowite)
• Mapa, podana w postaci Hzestawów Wcyfr ( 0- 9), w dowolnym dogodnym formacie (lista 2D, ciąg oddzielony znakami nowej linii itp.)

Wydajność

• Najkrótszy czas potrzebny na odwiedzenie każdego szczytu i powrót do punktu początkowego (liczba całkowita)

Warunki

• Wysokość danego obszaru jest reprezentowana przez cyfrę od 0do 9.
• „Szczyt” jest definiowany przez obszar o najwyższej wysokości.
• Ścieżka musi zaczynać się i kończyć w lewym górnym rogu (0,0) .
• Możesz poruszać się tylko do obszarów sąsiadujących z twoim bieżącym obszarem i nie możesz poruszać się po przekątnej.
  • Przejście z jednego obszaru do drugiego zajmuje 3 minuty, jeśli nie ma zmiany wysokości.
  • Wspinaczka zajmuje 11 minut ; to znaczy przejście z jednego obszaru do drugiego, który jest dokładnie o 1jednostkę wyżej.
  • Zejście zajmuje 2 minuty ; to znaczy, przejście z jednego obszaru do drugiego, który jest dokładnie o 1jednostkę niższy.
  • Nie możesz poruszać się w obszarach, które są wyższe niż 1jednostka wyżej lub niżej niż gdzie jesteś. (Nie można przejść z obszaru o wysokości 1do, na przykład, sąsiedniego obszaru z wysokością 3)
• Droga do wszystkich szczytów jest gwarantowana
• Maksymalna liczba pików wynosi 15.

Próbki

Wkład

4 5
32445
33434
21153
12343

Wydajność

96

Wyjaśnienie

Zaczynasz w lewym górnym rogu 3. Musisz odwiedzić dwa 5s, które są zlokalizowane na (0,4)i (3,3)i wrócić do 3na (0,0)w jak najkrótszym czasie.

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

Wkład

2 7
6787778
5777679

Wydajność

75

Mathematica 745 681 bajtów

Podstawową ideą jest wykonanie ważonego wykresu możliwych ruchów. Ciężary to czas potrzebny na przejście z jednego miejsca do drugiego. Ścieżka o najmniejszej wadze będzie najszybsza.

Cyfry wejściowe są umieszczane w prostokątnej tablicy r przez c (rzędy po kolumnach), a następnie w grę wchodzą trzy różne reprezentacje: (1) wykres siatki r przez c, gdzie każdy wierzchołek odpowiada komórce w tablicy, (2) (r c) według (r c) ważonej macierzy przylegania, która przechowuje wagi odpowiadające czasowi potrzebnemu (2, 3 lub 11 minut) na przejście z jednego miejsca (na wykresie siatki) do drugiego, oraz (3) ukierunkowane , ważony wykres przyległości zbudowany z macierzy.

Wykres siatki pomaga określić, które komórki (tj. Które wierzchołki) są możliwe do osiągnięcia z każdego wierzchołka - „możliwe do osiągnięcia”, ponieważ sąsiednia komórka musi znajdować się nie tylko w prawo, w lewo, powyżej lub poniżej danej komórki. Jego wartość musi również znajdować się w odległości 1 jednostki odległości od sąsiada (np. 3 nie łączy się z sąsiadującą 5 lub 1). Jeśli wierzchołek anie jest połączony z wierzchołkiem, bwówczas komórki macierzy przylegania {a, b} i {b, a} będą miały wartość ∞. Odpowiednio, ważony wykres przylegania nie będzie miał krawędzi od a do b, ani od b do a.

Ważony wykres sąsiedztwa służy do określenia minimalnej odległości ( GraphDistance) i najkrótszej trasy między dowolnymi wierzchołkami. Optymalna ścieżka musi zaczynać się od 1, dotknąć każdego ze szczytów i powrócić do 1. W tym przypadku „najkrótsza trasa” niekoniecznie musi oznaczać najmniej ruchów. Jest to ten, który ma najkrótszy całkowity czas, mierzony wagami krawędzi.

Grał w golfa

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

Dłuższa, bardziej czytelna forma

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

Testy

weights["4 5
 32445
 33434
 21153
 12343"]

96

weights@"2 7
 6787778
 5777679"

75

weights@"3 4
 1132
 2221
 1230"

51

Wyjaśnienie

Pomyśl o wierszach 2–5 poniższego tekstu

"4 5
 32445
 33434
 21153
 12343"

jako reprezentujący tablicę z 4 wierszami i 5 kolumnami:

gdzie każdy wierzchołek odpowiada cyfrze z tablicy wejściowej: 3 jest w wierzchołku 1, 2 jest w wierzchołku 2, 4 jest w wierzchołku 3, kolejne 4 w wierzchołku 4, 5 w wierzchołku 5 itp. Wykres siatki jest jedynie przybliżony przybliżenie wykresu, do którego dążymy. To jest bezkierunkowe. Ponadto niektóre krawędzie będą niedostępne. (Pamiętaj: nie możemy przejść z pozycji, która jest większa niż 1 jednostka wysokości powyżej lub poniżej bieżącej). Ale wykres siatki pozwala nam łatwo znaleźć te wierzchołki, które znajdują się obok dowolnego wybranego wierzchołka. Zmniejsza to liczbę krawędzi, które musimy wziąć pod uwagę, w pierwszym przykładzie (siatka 4 na 5), ​​z 400 (20 * 20) do 62 (31 * 2 to liczba krawędzi na wykresie siatki). W tym samym przykładzie działa tylko 48 krawędzi; 14 nie są.

Kolejna ważona macierz przylegania 20 na 20 reprezentuje odległość między wszystkimi parami wierzchołków od wykresu siatki.

Kod klucza, który decyduje o numerze, który ma zostać przypisany, znajduje się poniżej.

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

Komórka {1,2} - w jednym indeksowaniu - zawiera wartość 2, ponieważ przejście z wierzchołka 1 do wierzchołka 2 jest w dół. Komórka {2,1} zawiera 11, ponieważ przejście z wierzchołka 2 do wierzchołka 1 jest pod górę. Trójki w komórkach {1,6} i {6,1} oznaczają, że ruch nie jest ani w górę, ani w dół. Komórka {1,1} zawiera ∞, ponieważ nie jest połączona z samym sobą.

Poniższy wykres pokazuje strukturę leżącą u podstaw powyższego wejścia. Kolorowe strzałki pokazują optymalną ścieżkę od wierzchołka 1 do szczytów (w 5 i 14) i z powrotem do 1. Niebieskie strzałki odpowiadają ruchom na tym samym poziomie (3 min); czerwone strzałki oznaczają wejście (11 minut), a zielone strzałki wskazują zejście (2 minuty).

Ścieżka od wierzchołka 1 (komórka {1,1} do dwóch pików iz powrotem do wierzchołka 1:

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

96

Pyth, 92 bajty

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

Format wejściowy jest DICT mapowania współrzędne wysokościach {(0, 0): 3, (0, 1): 2, (0, 2): 4, …}. Znajduje najszybsze ścieżki między wszystkimi parami punktów za pomocą algorytmu Floyda – Warshalla , a następnie minimalizuje całkowity czas pożądanego cyklu we wszystkich permutacjach szczytów.

Wypróbuj online