Diberikan matriks yang terdiri dari bilangan bulat positif, output jalan dengan jumlah terendah ketika melintasi dari elemen kiri atas ke kanan bawah. Anda dapat bergerak secara vertikal, horizontal dan diagonal. Perhatikan bahwa mungkin untuk bergerak ke atas / bawah, kanan / kiri dan diagonal ke semua sisi.
Contoh:
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*
Jalur yang memberikan jumlah terendah ditandai dengan tanda bintang, dan menghasilkan jumlah berikut: 1 + 4 + 1 + 1 + 1 + 5 + 1 + 9 = 23 .
Kasus uji:
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)
Ini adalah kode-golf sehingga kode terpendek dalam setiap bahasa menang.
code-golf
number
graph-theory
optimization
matrix
Stewie Griffin
sumber
sumber
Jawaban:
JavaScript,
442 412 408358 byteIni adalah pengiriman PPCG pertama saya. Umpan balik akan sangat dihargai.
Ini membutuhkan array multi dimensi sebagai input.
Penjelasan
Pada dasarnya, loop melalui semua sel berulang-ulang menyesuaikan biaya terendah yang diketahui untuk sampai ke masing-masing tetangga. Akhirnya, grid akan mencapai keadaan di mana total biaya untuk mencapai bagian kanan bawah adalah biaya terendah untuk sampai ke sana.
Demo
Sunting: Terima kasih khusus kepada @ETHproductions karena membantu saya mencukur lusinan byte lezat.
Terima kasih lagi kepada @Stewie Griffin untuk tips Anda yang membuat 50 byte.
sumber
}
yang menyimpan beberapa byte. Anda juga tidak perlu mendeklarasikan variabel Anda; Saya pikir menghapusvar
s akan menghemat total 24 byte lebih.m[v][t]
sebagai variabel:t=x+X;v=y+Y;k=m[v][t]
akan lebih pendek ...?Python 3 + numpy + scipy ,
239222186 byteCobalah online!
sumber
Paket Octave + Image Processing,
175162157151142139 byteDisimpan 14 byte berkat @Luis Mendo dan 1 byte terima kasih ke @notjagan
Menggunakan paket Pemrosesan Gambar, karena mengapa tidak? Bukankah begitu bagaimana semua orang memecahkan masalah grafik?
Cobalah online!
Meledak
Penjelasan
Diberikan sejumlah bobot:
Inisialisasi array biaya sehingga biaya untuk mencapai setiap elemen adalah Infinity, kecuali titik awal (elemen kiri atas) yang harganya sama dengan bobotnya.
Ini adalah iterasi 0. Untuk setiap iterasi berikutnya, biaya untuk mencapai sel ditetapkan ke minimum:
Setelah iterasi pertama, biaya path ke elemen (2,2) (menggunakan indeks berbasis 1) akan menjadi
Array biaya penuh setelah iterasi pertama adalah:
Setelah iterasi
k
, setiap elemen akan menjadi biaya terendah untuk mencapai elemen itu sejak awal mengambilk
langkah paling banyak . Misalnya, elemen di (3,3) dapat dicapai dalam 2 langkah (iterasi) dengan biaya 22:Tetapi pada iterasi ke-4, jalur 4 langkah ditemukan dengan biaya 20:
Karena tidak ada jalur melalui matriks mxn bisa lebih panjang dari jumlah elemen dalam matriks (sebagai batas atas yang sangat longgar), setelah
m*n
iterasi setiap elemen akan mengandung biaya jalur terpendek untuk mencapai elemen tersebut dari awal.sumber
while
dan~
.while
kefor
dan masih bisa menggunakan tip Anda. Terima kasih!JavaScript, 197 byte
Mendandani:
sumber
Mathematica 279 Bytes
Ide dasarnya adalah membuat grafik dengan simpul yang sesuai dengan entri matriks dan tepi terarah antara dua simpul yang dipisahkan oleh
ChessboardDistance
lebih besar dari nol tetapi kurang dari atau sama dengan 1. Kebetulan, ini dikenal sebagai grafik Raja , karena sesuai dengan langkah sah seorang raja di papan catur.FindShortestPath
ini kemudian digunakan untuk mendapatkan jalur minimal. Ini berfungsiEdgeWeight
, tidakVertexWeight
, jadi ada beberapa kode tambahan untuk didefinisikanEdgeWeight
sebagai entri matriks yang sesuai dengan tujuan setiap tepi yang diarahkan.Kode:
Perhatikan bahwa
karakter adalah simbol transpose. Ini akan menempel ke Mathematica apa adanya.Pemakaian:
Keluaran:
Jika Anda mengatur
g=Graph[...,GraphLayout->{"GridEmbedding","Dimension"->d},VertexLabels->Thread[s->m]
danp=FindShortestPath[...
kemudian grafik berikut akan secara visual menampilkan solusi (bagian atas matriks sesuai dengan bagian bawah grafik):sumber
Haskell, 228 byte
Posisi adalah daftar dari dua elemen, karena itu mudah dibuat dengan
sequence
dan sama mudahnya dengan pola yang cocok dengan 2-tupel.Mulai pada
-1,-1
dan hitung biaya setiap langkah bidang tujuan.Alternatif dua baris pertama: mulai dari
0,0
, hitung bidang keberangkatan, berakhir pada koordinat yang sama dengan dimensi matriks (jadi turun kanan dari tujuan, yang perlu ditambahkan ke daftar tujuan hukum) - persis sama panjang tetapi lebih lambat:Menggunakan infix untuk
map
tidak menghemat byte di sini, tetapi saya menggantinya segera setelah itu tidak memerlukan biaya satu, karena itu hanya bisa lebih baik dengan lebih banyak menggunakan, dan kadang-kadang dengan restrukturisasi lain juga yang memotong sepasang kurung lainnya.Untuk ditingkatkan: Redundan
filter
s. Penggabungan / di-lapisan mereka untukfilter(flip elem$(s$(\x->[0..x])#m)\\p)
denganimport Data.List
untuk\\
biaya 3 byte.Juga, terlalu buruk
(fromEnumTo 0)
adalah 2 byte lebih lama dari(\x->[0..x])
.sum$concat c
adalah semua biaya bidang diringkas dan dengan demikian batas atas yang dapat diungkapkan secara singkat pada biaya jalur yang diberikan kepadaminimum
untuk menghindari daftar kosong (pemeriksa tipe saya telah menentukan semuanya untuk dikerjakan padaInteger
s, jadi tidak ada hard-coding maksimum , hehe). Tidak peduli bagaimana saya membatasi langkah-langkah berdasarkan yang dibuat sebelumnya (yang akan mempercepat banyak algoritma, tetapi juga biaya byte), saya tidak dapat menghindari jalan buntu yang membuat ini diperlukan kembali mundur.Satu gagasan filter adalah
((not.e n).zipWith(-)(head r))
dengan mengekstraksin=s[[-1..1],[-1..1]]
, yang mengharuskan penambahan,[-1,-1]
ke jalur awal. Algoritme kemudian menghindari pergi ke tempat yang seharusnya sudah ada pada langkah sebelumnya, yang membuat menginjak bidang tepi secara orthogonal ke tepi itu menjadi jalan buntu.Lain adalah
((>=0).sum.z(*)d)
dengan mengekstraksiz=zipWith
, yang memperkenalkan argumen barud
pada fungsi rekursif yang diberikan seperti(z(-)p q)
pada rekursi dan[1,1]
dalam kasus awal. Algoritme menghindari langkah-langkah berurutan dengan produk skalar negatif (d
menjadi langkah sebelumnya), yang berarti tidak ada putaran tajam 45 °. Ini masih mempersempit pilihan, dan menghindari jalan buntu sepele sebelumnya, tetapi masih ada jalan yang berakhir tertutup di bidang yang sudah dikunjungi (dan mungkin 'pelarian' yang bagaimanapun akan berbelok tajam).sumber
Python 2,
356320 byteCoba di sini!
-36 bytes terima kasih kepada notjagan !
Menerima daftar daftar sebagai input, dan mengeluarkan biaya terendah saat menavigasi matriks dari kiri atas ke kanan bawah.
Penjelasan
Temukan setiap rute yang mungkin dari kiri atas ke kanan bawah dari matriks, buat daftar koordinat x, y untuk setiap rute. Rute tidak dapat mundur, dan harus berakhir pada
(len(s)-1,len(s[0])-1)
.Jumlahkan bilangan bulat pada setiap jalur koordinat, dan kembalikan biaya minimum.
The
print
dapat dengan mudah diubah ke output daftar koordinat untuk rute terpendek.sumber
or
conditional. Terima kasih!APL (Dyalog Classic) , 33 byte
Cobalah online!
{ }
berfungsi dengan argumen⍵
+\+⍀⍵
mengambil jumlah parsial demi baris dan kolom untuk menetapkan batas atas pesimis pada jarak jalur( )⍣≡
ulangi sampai konvergensi:(⍉3⌊/⊣/,⊢,⊢/)⍣2
min jarak ke tetangga, yaitu lakukan dua kali (( )⍣2
): kolom paling kiri (⊣/,
) ke self (⊢
) dan tambahkan kolom paling kanan (,⊢/
), cari minima dalam tripel horizontal (3⌊/
) dan transpos (⍉
)⍵+
tambahkan nilai setiap node ke jarak min ke tetangga⊢⌊
cobalah untuk mengalahkan jarak terbaik saat ini⊃⌽,
Akhirnya, kembalikan sel kanan bawahsumber