Kura-kura ingin bergerak di sepanjang grid untuk mendapatkan makanannya. Dia ingin tahu berapa banyak gerakan yang diperlukan baginya untuk sampai ke sana.
Selain itu karena dia lambat dia memiliki teleporter yang didirikan di sekitar domainnya yang akan dia gunakan jika jalurnya lebih pendek. Atau hindari jika itu memperpanjang jalannya.
Temui kura-kura
🐢
Kura-kura hidup di atas kisi
Kura-kura dapat pindah ke sembarang kotak ...
Namun, kura-kura tidak dapat bergerak ke bujur sangkar dengan gunung
Kura-kura ingin memakan Strawberry-nya, dan ingin tahu berapa lama untuk mencapai Strawberry-nya
Tantangan
Mengingat output konfigurasi grid awal jumlah gerakan itu akan mengambil kura-kura untuk mencapai strawberry-nya.
Aturan
Anda dapat berasumsi bahwa kisi input memiliki solusi
Setiap kotak hanya akan memiliki satu
strawberry
dan duaportals
dan satuturtle
Kotak input dapat dimasukkan dalam format apa pun yang nyaman
Anda harus memperlakukan
teleporters
item sekali pakaiGiliran penyu yang bergerak ke
teleporter
kotak dia sudah di sesuaiteleporter
. Dia tidak pernah pindah keteleporter
dan tinggal di sana untuk bergerakJalur terpendek tidak perlu menggunakan portal
Kura-kura tidak bisa melewati ubin gunung
Anda dapat menggunakan karakter ASCII atau integer untuk mewakili
mountains
,turtle
,empty grid square
,strawberry
Anda dapat menggunakan karakter yang sama atau dua karakter ASCII yang berbeda atau bilangan bulat untuk mewakili
teleporter
pasanganGrid dapat memiliki lebih dari satu jalur dengan panjang jalur terpendek yang sama
Ini adalah kode-golf
Klarifikasi terhadap Aturan
- Anda harus memperlakukan
teleporters
item sekali pakai.
Alasan : bahwa kasus:
Bisa hanya dipecahkan dengan memasukkan dan keluar portal dua kali. Pada saat membuat klarifikasi ini, kedua solusi bertindak dengan mengasumsikan bahwa keduanya adalah penggunaan tunggal, atau tidak ada alasan untuk mencoba kotak yang sebelumnya digunakan. Untuk menghindari pemecahan solusi kerja keras mereka, ini sepertinya cara terbaik untuk pengaturan ini. Oleh karena itu, ini akan dianggap sebagai grid yang tidak valid.
Kasus Uji diformat sebagai daftar
[ ['T', 'X', 'X', 'S', 'X'], ['X', 'X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X', 'X'] ] --> 3
[ ['T', 'M', 'X', 'S', 'X'], ['X', 'M', 'X', 'X', 'X'], ['O', 'X', 'X', 'X', 'O'] ] --> 4
[ ['T', 'M', 'X', 'S', 'O'], ['O', 'M', 'X', 'X', 'X'], ['X', 'X', 'X', 'X', 'X'] ] --> 2
[ ['T', 'M', 'X', 'S', 'X'], ['O', 'M', 'X', 'X', 'X'], ['O', 'X', 'X', 'X', 'X'] ] --> 4
[ ['T', 'M', 'S', 'X', 'O'], ['X', 'M', 'M', 'M', 'M'], ['X', 'X', 'X', 'X', 'O'] ] --> 7
[ ['T', 'X', 'X', 'S', 'X'], ['O', 'M', 'M', 'M', 'X'], ['X', 'X', 'O', 'X', 'X'] ] --> 3
Test Case diformat untuk manusia
T X X S X
X X X X X
X X X X X --> 3
T M X S X
X M X X X
O X X X O --> 4
T M X S O
O M X X X
X X X X X --> 2
T M X S X
O M X X X
O X X X X --> 4
T M S X O
X M M M M
X X X X O --> 7
T X X S X
O M M M X
X X O X X --> 3
Kredit
Desain dan struktur melalui: Mouse lapar oleh Arnauld
Usulan Tantangan Sunting Saran: Kamil-drakari , beefster
sumber
Jawaban:
JavaScript (ES7),
140 139138 byteMengambil input sebagai matriks bilangan bulat dengan pemetaan berikut:
Cobalah online!
Bagaimana?
Fungsi pencarian rekursif utama dapat mencari ubin tertentu di papan (jika itu disebut dengan ) atau untuk ubin apa pun di yang dapat dicapai dari posisi saat ini .g t t≠0 (x,y) (X,Y)
Ini melacak panjang jalur saat ini di dan memperbarui hasil terbaik to setiap kali kura-kura menemukan strawberry.i R min(R,i)
Ini pertama kali disebut dengan untuk menemukan posisi awal kura-kura.t=2
Ia menyebut dirinya sendiri dengan jika suatu portal tercapai, sehingga kura-kura tersebut diteleportasikan ke portal lainnya. Kami tidak menambah selama iterasi seperti itu.t=−1 i
Setiap ubin yang dikunjungi sementara diatur ke gunung untuk mencegah kura-kura bergerak dua kali pada ubin yang sama di jalur yang sama. Jika kita terjebak dalam buntu, rekursi hanya berhenti tanpa memperbarui .R
Berkomentar
sumber
Python 2 ,
441431341 byteCobalah online!
Masukkan sebagai daftar, tetapi gunakan angka sebagai ganti karakter (terima kasih kepada Quintec) dan nilai terpisah untuk tujuan teleporter. Lekukan besar itu harus berupa karakter tab jika Stack Exchange menghapusnya. Setiap tips atau ide sangat disambut, karena saya merasa ini bisa menjadi
jauhlebih pendek.Tabel untuk karakter yang digunakan dalam tantangan angka yang digunakan untuk program saya ada di bawah, tetapi Anda juga dapat menggunakan program ini .
-10 byte terima kasih kepada Quintec dengan mengubah input dari menggunakan karakter menjadi angka.
-Banyak byte berkat Jonathan Frech, ElPedro, dan Jonathan Allan.
sumber
Python 2 , 391
397403422byteCobalah online!
Masalahnya diterjemahkan ke dalam grafik dan solusinya adalah menemukan jalur terpendek dari kura-kura ke stroberi.
sumber