Memecahkan Labirin Angka-Pelompat

Anak saya yang berusia 8 tahun bosan membuat labirin konvensional, dan telah membuat varian yang terlihat seperti ini:

Idenya adalah mulai dari x dan mencapai o melalui aturan normal. Selain itu, Anda dapat "hop" dari setiap bilangan bulat untuk setiap bilangan bulat lainnya b , tetapi Anda harus membayar | a - b | dolar untuk hak istimewa. Tujuannya adalah untuk memecahkan labirin dengan biaya paling murah. Pada contoh di atas, kita bisa beralih dari x ke o melalui x-14-18-27-28-o dengan biaya 5, tetapi lebih murah untuk pergi x-13-11-9-8-29-28-o hanya untuk 4.$a$$b$$|a-b|$

Jadi, inilah pertanyaan saya: apa solusi terbaik (dalam hal waktu berjalan asimptotik) yang dapat Anda pikirkan untuk menyelesaikan ini? Anda dapat membuat asumsi yang masuk akal tentang format input.

Catatan: Saya menggunakan tag "puzzle" di sini karena saya memiliki jawaban , tetapi saya tidak yakin itu optimal dan ingin melihat apakah ada orang lain yang dapat meningkatkan solusi saya. (Di sini n adalah jumlah bilangan bulat di labirin.)$O(n^2)$$n$

$O(n\log n)$$y$$y$$y_-$$y_+$$y$$y$

Pembaruan ini cukup untuk menjaga tumpukan mengembalikan elemen minimum karena setiap simpul terdekat Anda melompat harus secara numerik tepat di atas atau tepat di bawah simpul yang sudah dikunjungi.

$y_-$$y_+$$O(n \log n)$$O(n)$$O(n \log n)$$O(n \log n)$

$O(n^2)$

Tampaknya wajar untuk mengubah ini menjadi masalah jalur terpendek dengan simpul awal khusus (x) dan simpul akhir (0). Akan ada satu simpul lain untuk masing-masing angka. Baik x dan 0 memiliki tepi bobot 0 ke semua node angka yang dapat dijangkau dalam labirin. Semua node angka terhubung dengan bobot 0 (jika jumlahnya dapat dicapai oleh maze) atau dengan perbedaan antara angka (jika tidak dapat dicapai oleh maze).

$O(n^2)$$n^2$$O(n^2)$