Diberi kisi-kisi arah dan posisi awal dan akhir, tentukan jumlah minimum penggantian dalam kisi arah yang perlu dibuat untuk menyelesaikan jalur antara dua titik. Kisi-kisi adalah dua silinder. Ini lebih jelas diberi contoh.
Contoh
Mari kita ambil kotak berikut sebagai contoh:
>>>>v
>>>><
<<<<<
Mari kita mulai dari (1, 1)
dan berakhir pada (1, 3)
( di mana koordinat berada (x, y)
atau (col, row)
, dengan baris atas dan kolom kiri berada 1
). Kemudian, satu solusi yang mungkin adalah mengganti (1, 1)
and (1, 2)
dengan v
, sehingga kisi terakhir terlihat seperti ini:
v>>>v
v>>><
<<<<<
Mulai dari (1, 1)
, jalan menuju kita (1, 3)
. Namun, ada solusi yang lebih pendek, yang akan diganti (5, 2)
dengan v
, jadi kisi terakhir adalah ini:
>>>>v
>>>>v
<<<<<
Mulai dari (1, 1)
, jalan yang agak panjang menuju (1, 3)
.
Mengganti apa pun di baris atas dengan ^
karya juga (terima kasih @Spitemaster).
Memasukkan
Input akan terdiri dari kisi-kisi empat kemungkinan nilai, serta dua koordinat. Anda dapat mengambil kotak dalam format apa pun yang masuk akal; misalnya, karakter atau matriks integer, daftar string, dll. Anda juga dapat meminta dimensi kisi. Anda dapat mengambil koordinat dalam format apa pun yang wajar; misalnya, pasangan bilangan bulat, bilangan kompleks, dll. Anda dapat memilih pengindeksan 0 atau 1.
Keluaran
Output harus berupa bilangan bulat tunggal, jumlah minimal penggantian grid yang diperlukan untuk menutup jalur dari awal hingga akhir.
Aturan dan Spesifikasi
- Celah Standar Berlaku
- kisi-kisi itu berlipat ganda, artinya bergerak ke atas dari atas ke bawah, kiri dari kiri ke kanan, dll.
Contoh Kasus
Kasus sampel diberikan sebagai matriks karakter dan koordinat 1-diindeks.
Kasus 1
Memasukkan
>>>>v
>>>><
<<<<<
1 1
1 3
Keluaran
1
Penjelasan
Lihat contoh.
Kasus 2
Memasukkan
<<<<<
v>v>v
>>>>>
1 1
5 3
Keluaran
1
Penjelasan
Anda dapat mengganti (1, 1)
dengan v
atau (2, 1)
dengan v
. Dalam kasus pertama, mulai dari (1, 1)
, jalan lurus ke bawah dan kemudian ke kanan ke tujuan. Dalam kasus kedua, jalur loop dari kiri ke kanan, mencapai (2, 1)
, turun, kanan, bawah, dan kemudian kanan sampai menyentuh tujuan.
Kasus 3
Memasukkan
^^^^^^
><<>>>
vvvvvv
2 2
5 2
Keluaran
2
Penjelasan
Perubahan terbaik adalah membuat baris tengah membungkus kiri ke titik; yaitu, buat item pertama dan terakhir di baris tengah <
. Atau, buat 2 2
dan 3 2
keduanya >
.
Ini adalah tantangan kode-golf , jadi kode terpendek menang!
sumber
^
atauv
.><
lakukan itu ping pong bolak-balik (sehingga kedua posisi tiba di) atau apakah seperti ada dinding di antara mereka?Jawaban:
JavaScript (ES6),
140135 byteMengambil input sebagai
(a, width, height, x1, y1)(x0, y0)
manaa[]
adalah matriks bilangan bulat dan semua koordinat 0-diindeks.Arah: untuk kiri , untuk atas , untuk kanan dan untuk bawah .−2 - 1 0 1−1 0 1
Cobalah online!
Bagaimana?
Kami menggunakan pencarian pertama untuk mencoba semua jalur yang mungkin dari ke tanpa mengunjungi dua kali sel yang sama.(x,y) (X,Y)
Kami melacak berapa kali mana arah yang dipilih tidak sesuai dengan arah yang disimpan dalam matriks input.n
Kami akhirnya mengembalikan , yang didefinisikan sebagai nilai minimum .m n
sumber
Jelly ,
7372 byteCobalah online!
Contoh menggunakan case 3 yang membutuhkan dua perubahan (juga memiliki footer untuk menerjemahkan ke
><v^
dalam angka).Program lengkap yang mengharapkan argumen berikut:
Kiri: daftar dua daftar; pertama-tama grid arah yang rata dikodekan sebagai 1 = kanan, 2 = kiri, 3 = bawah, 4 = atas, diikuti oleh daftar posisi akhir dan mulai posisi sebagai indeks-nol [baris, kolom]. Sebagai contoh pertama
[1,1,1,1,3,1,1,1,1,4,2,2,2,2,2],[[2,0],[0,0]]
,.Kanan: daftar jumlah baris yang diikuti oleh kolom. Sebagai contoh pertama
[3,5]
Mengembalikan jumlah perubahan yang diperlukan untuk memulai dari awal hingga akhir. Lambat sekali ini lebih dari satu perubahan. Pada TIO, contoh kasus ketiga membutuhkan sekitar. 30 detik untuk selesai.
Penjelasan lengkap di bawah, tetapi gambaran umum adalah:
Penjelasan lengkap:
sumber