Saya berdiri di titik (0,0)di peta Hx di Wmana ketinggian diwakili oleh angka, misalnya:

1132
2221
1230    # H = 3, W = 4

Saya ingin menikmati pemandangan dari setiap puncak, yang dalam hal ini adalah area dengan ketinggian 3. Namun, mendaki bukit bukanlah tugas yang mudah, dan saya juga kehabisan waktu.

Tantangan

Tantangannya adalah menemukan jalan tercepat untuk mengunjungi semua puncak dan kembali.

Kemenangan program terpendek.

Memasukkan

• H, W - tinggi dan lebar peta (Integer) (opsional, dapat berupa daftar / tuple atau dua input integer terpisah)
• Peta, diberikan sebagai Hset Wdigit ( 0- 9), dalam format apa pun yang nyaman (daftar 2D, string dipisahkan oleh baris baru, dll.)

Keluaran

• Waktu terpendek untuk mengunjungi setiap puncak dan kembali ke titik awal Anda (Integer)

Kondisi

• Ketinggian area tertentu diwakili oleh digit dari 0hingga 9.
• "Puncak" ditentukan oleh area dengan ketinggian tertinggi.
• Jalur harus dimulai dan berakhir di area kiri atas (0,0) .
• Anda hanya dapat pindah ke area yang berdekatan dengan area Anda saat ini, dan Anda mungkin tidak bergerak secara diagonal.
  • Dibutuhkan 3 menit untuk berpindah dari satu area ke area lain jika tidak ada perubahan ketinggian.
  • Butuh 11 menit untuk mendaki; yaitu, bergerak dari satu area ke area lain yang persis 1lebih tinggi satuannya.
  • Dibutuhkan 2 menit untuk turun; yaitu, pindah dari satu area ke area lain yang persisnya 1unit lebih rendah.
  • Anda tidak dapat pindah ke area yang lebih dari 1unit lebih tinggi atau lebih rendah dari tempat Anda berada. (Anda tidak dapat pergi dari suatu daerah dengan ketinggian 1ke daerah yang berdekatan dengan ketinggian, katakanlah, 3)
• Jalur ke semua puncak dijamin
• Jumlah puncak maksimum adalah 15.

Sampel

Memasukkan

4 5
32445
33434
21153
12343

Keluaran

96

Penjelasan

Anda mulai dari kiri atas 3. Anda harus mengunjungi dua 5s yang terletak di (0,4)dan (3,3)dan kembali ke 3di (0,0)dalam waktu sesingkat mungkin.

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

Memasukkan

2 7
6787778
5777679

Keluaran

75

Mathematica 745 681 bytes

Ide dasarnya adalah membuat grafik tertimbang dari kemungkinan pergerakan. Bobot adalah waktu yang diperlukan untuk berpindah dari satu tempat ke tempat lain. Jalan dengan bobot paling sedikit akan menjadi yang tercepat.

Digit input ditempatkan dalam larik persegi panjang r by c (rows by kolom) dan kemudian tiga representasi berbeda berperan: (1) grafik grid r by c, di mana setiap titik bersesuaian dengan sel dalam array, (2) (r c) dengan (r c) matriks adjacency tertimbang yang menahan bobot sesuai dengan waktu yang dibutuhkan (2, 3, atau 11 menit) untuk berpindah dari satu lokasi (dalam grafik kisi) ke lokasi lain, dan (3) diarahkan , grafik kedekatan tertimbang dibangun dari matriks.

Grafik kisi membantu menentukan sel mana (yaitu simpul mana) yang mungkin dapat dijangkau dari masing-masing simpul - "mungkin dapat dijangkau" karena sel tetangga tidak boleh hanya sel kanan, kiri, atas atau di bawah sel yang diberikan. Nilainya juga harus berada dalam 1 unit jarak dari tetangga (mis., 3 tidak terhubung ke tetangga 5 atau 1). Jika simpul atidak terhubung ke simpul bmaka sel-sel matriks adjacency {a, b} dan {b, a} akan memiliki nilai ∞. Dengan demikian, grafik adjacency tertimbang tidak akan memiliki ujung dari a ke b, atau dari b ke a.

Grafik adjacency tertimbang berfungsi untuk menentukan jarak minimum ( GraphDistance) dan rute terpendek antara setiap simpul. Jalur optimal harus dimulai dengan 1, menyentuh masing-masing puncak, dan kembali ke 1. Dalam hal ini, "rute terpendek" tidak harus dengan rute dengan pergerakan paling sedikit. Ini adalah satu dengan waktu keseluruhan terpendek, diukur dalam bobot tepi.

Golf

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

Bentuk yang lebih panjang dan lebih mudah dibaca

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

Tes

weights["4 5
 32445
 33434
 21153
 12343"]

96.

weights@"2 7
 6787778
 5777679"

75.

weights@"3 4
 1132
 2221
 1230"

51.

Penjelasan

Pikirkan baris 2-5 dari input berikut

"4 5
 32445
 33434
 21153
 12343"

mewakili array dengan 4 baris dan 5 kolom:

di mana setiap titik bersesuaian dengan digit dari array input: 3 berada di titik 1, 2 di titik 2, 4 di titik 3, 4 di titik 4, 5 di titik 5, dll. Grafik grid hanya kasar perkiraan grafik yang kami tuju. Itu tidak diarahkan. Selain itu, beberapa tepi tidak akan tersedia. (Ingat: kita tidak dapat berpindah dari posisi ke posisi lain yang lebih dari 1 satuan ketinggian di atas atau di bawah posisi saat ini.) Tetapi grafik kisi mari kita dengan mudah menemukan simpul yang berada di sebelah setiap simpul yang dipilih. Ini mengurangi jumlah sisi yang perlu kita pertimbangkan, pada contoh pertama (kisi 4 dengan 5), dari 400 (20 * 20) menjadi 62 (31 * 2 adalah jumlah tepi dalam grafik kisi). Dalam contoh yang sama, hanya 48 sisi yang beroperasi; 14 tidak.

Matriks adjacency tertimbang 20 kali 20 berikut mewakili jarak antara semua pasangan simpul dari grafik kisi.

Kode kunci yang menentukan nomor yang akan ditugaskan di bawah.

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

Sel {1,2} - dalam satu-pengindeksan - berisi nilai 2 karena perpindahan dari titik 1 ke titik 2 menurun. Sel {2,1} berisi 11 karena perpindahan dari titik 2 ke titik 1 adalah menanjak. Angka 3 pada sel {1,6} dan {6,1} menandakan bahwa pergerakannya tidak naik atau turun. Sel {1,1} berisi ∞ karena tidak terhubung dengan dirinya sendiri.

Grafik berikut menunjukkan struktur yang mendasari input di atas. Panah berwarna menunjukkan jalur optimal dari puncak 1 ke puncak (pada 5 dan 14) dan kembali ke 1. Panah biru sesuai dengan gerakan pada tingkat yang sama (3 menit); panah merah berarti pendakian (11 menit) dan panah hijau menunjukkan keturunan (2 menit).

Path dari vertex 1 (sel {1,1} ke dua puncak dan kembali ke vertex 1:

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

96

Pyth, 92 byte

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

Format input adalah dict pemetaan koordinat ke ketinggian: {(0, 0): 3, (0, 1): 2, (0, 2): 4, …}. Ini menemukan jalur tercepat antara semua pasangan titik menggunakan algoritma Floyd-Warshall , kemudian meminimalkan waktu total dari siklus yang diinginkan atas semua permutasi puncak.

Cobalah online