Memasukkan:
Labirin berisi karakter:
--
(dinding horizontal);|
(dinding vertikal);+
(koneksi);(ruang berjalan);
I
(jalan masuk);U
(keluar).
Ie input bisa terlihat seperti ini:
+--+--+--+--+--+--+--+--+--+--+
I | | |
+ +--+--+--+ + + + +--+ +
| | | | | |
+--+--+--+ +--+--+ + + +--+
| | | | |
+ +--+--+ + +--+--+ +--+ +
| | | | | |
+--+ + +--+--+ +--+--+ + +
| | | | | |
+ +--+--+--+ +--+--+ + + +
| | | | | |
+--+ + +--+--+ +--+--+--+--+
| | | | |
+ + +--+--+--+ +--+ + + +
| | | | | | | |
+--+--+ + +--+ + + +--+ +
| | | | | |
+ +--+--+--+ + + + + +--+
| | | | U
+--+--+--+--+--+--+--+--+--+--+
Keluaran:
Yang paling efisien jalan Anda harus berjalan untuk mendapatkan dari pintu masuk ke pintu keluar dari labirin (melalui labirin), ditunjukkan oleh karakter menunjukkan kiri, kanan, atas dan bawah (yaitu >
; <
; ^
; v
).
Aturan tantangan:
- Anda dapat mengambil input dalam format apa pun yang masuk akal. String-array, String tunggal dengan baris baru, 2D char-array, dll. Semuanya merupakan format input yang memungkinkan.
- Output dapat terdiri dari empat karakter berbeda. Yaitu
><^v
;→←↑↓
;⇒⇐⇑⇓
;RLUD
;0123
;ABCD
; dll.) - Anda diizinkan untuk menambahkan spasi atau mengikuti baris baru ke output jika diinginkan; ini opsional.
- Langkah-langkah dihitung per kotak (lihat empat-
+
simbol untuk kotak), dan bukan per karakter. - Labirin dapat berukuran 5x5 hingga 15x15, dan akan selalu berbentuk kotak (sehingga tidak akan ada uji kasus untuk labirin 5x10).
- Anda dapat mengasumsikan bahwa setiap labirin memiliki satu atau lebih jalur yang valid dari awal hingga akhir, dan Anda selalu menampilkan jalur terpendek (lihat kotak uji 4 dan 5).
- Jika ada beberapa jalur dengan panjang yang sama, Anda dapat memilih jalur mana yang akan di-output (lihat test case 6).
- Anda tidak dapat 'berjalan' di luar batas labirin (lihat kotak uji 7 dan 8).
Aturan umum:
- Ini adalah kode-golf , jadi jawaban tersingkat dalam byte menang.
Jangan biarkan bahasa kode-golf mencegah Anda memposting jawaban dengan bahasa non-codegolf. Cobalah untuk memberikan jawaban sesingkat mungkin untuk bahasa pemrograman 'apa saja'. - Aturan standar berlaku untuk jawaban Anda, jadi Anda diperbolehkan menggunakan STDIN / STDOUT, fungsi / metode dengan parameter yang tepat, program lengkap. Panggilanmu.
- Celah default tidak diperbolehkan.
- Jika memungkinkan, silakan tambahkan tautan dengan tes untuk kode Anda.
- Juga, silakan tambahkan penjelasan jika perlu.
Kasus uji:
1. Input:
+--+--+--+--+--+--+--+--+--+--+
I | | |
+ +--+--+--+ + + + +--+ +
| | | | | |
+--+--+--+ +--+--+ + + +--+
| | | | |
+ +--+--+ + +--+--+ +--+ +
| | | | | |
+--+ + +--+--+ +--+--+ + +
| | | | | |
+ +--+--+--+ +--+--+ + + +
| | | | | |
+--+ + +--+--+ +--+--+--+--+
| | | | |
+ + +--+--+--+ +--+ + + +
| | | | | | | |
+--+--+ + +--+ + + +--+ +
| | | | | |
+ +--+--+--+ + + + + +--+
| | | | U
+--+--+--+--+--+--+--+--+--+--+
1. Output:
>v>>>vv<v>>v>v>>vvv>>>
2. Input:
+--+--+--+--+--+
I | | |
+ +--+--+ + +
| | | |
+ +--+ + + +
| | | | |
+ + +--+ + +
| | |
+--+ + +--+--+
| | U
+--+--+--+--+--+
2. Output:
>vvv>>v>>>
3. Input:
+--+--+--+--+--+
U | |
+ + +--+--+ +
| | | |
+--+--+ + +--+
| | |
+ +--+--+--+ +
| | | |
+ + + + +--+
| | I
+--+--+--+--+--+
3. Output:
<<<^<v<^^>>^<^<<
4. Input (test case with two valid paths):
+--+--+--+--+--+
U | |
+ + +--+--+ +
| | |
+--+--+ + +--+
| | |
+ +--+--+--+ +
| | | |
+ + + + +--+
| | I
+--+--+--+--+--+
4. Output:
<<^>^<^<<^<< (<<<^<v<^^>>^<^<< is less efficient, and therefore not a valid output)
5. Input (test case with two valid paths):
I
+--+--+--+--+--+--+--+--+--+--+ +--+--+--+--+
| | | | |
+ + + +--+--+--+ + +--+--+ +--+--+ + +
| | | | | | | |
+--+--+--+ +--+ + +--+--+--+--+ +--+--+--+
| | | | | | | | |
+ + + + + +--+ + + + +--+--+ +--+ +
| | | | | | | |
+ +--+--+--+ +--+--+ + +--+ +--+--+ +--+
| | | | | | | | |
+ +--+ + +--+ +--+--+ +--+--+ + +--+ +
| | | | | | |
+ + +--+--+--+--+ + +--+--+--+ +--+ +--+
| | | | | | | |
+--+--+--+ + +--+--+ +--+ + +--+ +--+ +
| | | | | | | |
+ +--+--+--+--+ + + +--+--+--+ + + + +
| | | | | | | | | |
+--+ + + + + + +--+--+ + + +--+ + +
| | | | | | | | | |
+--+ +--+--+ + + + +--+--+--+ + + + +
| | | | | | | | | |
+ +--+ +--+--+ + +--+--+ + +--+ + + +
| | | | | | | | | |
+--+--+--+ + + +--+ + +--+--+ +--+ + +
| | | | | | | |
+ + +--+--+--+--+ +--+--+ +--+--+ +--+ +
| | | | | |
+ + + +--+--+--+--+--+--+--+--+ +--+ +--+
| | | |
+--+--+--+--+--+--+--+--+--+ +--+--+--+--+--+
U
5. Output:
v<<<v<vv<<v<v>>^>>^^>vvv>>>v>vv<vv<<v<v<^<^^^^<vvvvv<^<v<<v>v>>>>>>>v (v<<<v<vv<<v<v>>^>>^^>vvv>>>v>vv<vv<<v<v<^<^^^^<vvvvv>v>>>^>>^>^^>vvv<v<v<<v is less efficient, and therefore not a valid output)
6. Input:
+--+--+--+--+--+
I |
+ + + + + +
| |
+ + + + + +
| |
+ + + + + +
| |
+ + + + + +
| U
+--+--+--+--+--+
6. Output:
>>v>v>v>v> or >v>v>v>v>> or >>>>>vvvv> or etc. (all are equally efficient, so all 10-length outputs are valid)
7. Input:
I U
+ + +--+--+--+
| | | |
+ +--+--+ + +
| | | |
+--+ + +--+ +
| | | |
+ +--+ + + +
| | |
+--+ +--+--+ +
| | |
+--+--+--+--+--+
7. Output:
vv>v>^>^<<^
8. Input:
+--+--+--+--+--+
| | |
+ +--+ +--+ +
I | | | |
+ + +--+ + +
U | | | |
+--+--+ + + +
| | | |
+ +--+--+--+ +
|
+--+--+--+--+--+
8. Output:
>v<
Labirin dihasilkan menggunakan alat ini (dan dalam beberapa kasus sedikit dimodifikasi).
code-golf
path-finding
maze
Kevin Cruijssen
sumber
sumber
v<<<<<<^^^^^
(selalu berpikir di luar kotak)>v>>>vv<v>>v>v>>vvv>>>
.Jawaban:
Retina ,
338281275273261 byteCobalah online!
Catatan
0x20
) diganti dengan interpunct (·
) baik dalam jawaban ini dan tautan TIO. Program ini berfungsi dengan baik jika ruang dipulihkan.AvKr
untuk naik, turun, kiri, dan kanan, masing-masing. Itu bisa diganti dengan huruf apa pun kecualiI
.Memakan waktu sekitar 40 detik pada TIO untuk test case 15 × 15. Sabar.Mengolah bagian untuk menemukan jalur terpendek setelah jalan mencapai pintu keluar. Ternyata itu menyita banyak waktu.Penjelasan
Program ini terdiri dari 3 fase:
Format
Karena format labirin asli cukup sulit, bagian pertama dari program mengubahnya menjadi format lain.
Sel
Dalam format asli, setiap sel direpresentasikan sebagai wilayah 2 × 3:
Karena kolom kanan tidak berisi informasi, program mengidentifikasi sel-sel sebagai wilayah 2 × 2 dengan bagian
+
di kiri atas.Ini memberi kita 3 jenis sel:
U
dalam uji kasus 1 adalah dalam R-Cell.Dalam format baru, sel direpresentasikan sebagai string panjang variabel:
Dinding kiri dan atas disalin dari format aslinya. Nomor kolom didasarkan pada posisi horizontal sel dan digunakan untuk penyelarasan (mengidentifikasi sel langsung di atas / di bawah satu sama lain). Path adalah string alfabet yang digunakan selama fase isian untuk menyimpan jalur terpendek untuk mencapai sel itu. Penanda jalur dan keluar akan dijelaskan lebih lanjut.
Setengah sel
Meskipun sebagian besar labirin adalah sel, ada wilayah labirin yang bukan sel:
+
s di sepanjang dinding kanan tidak membentuk sel karena berada di kolom terakhir.+
di sebelah kiri mereka. Misalnya, pintu masukI
dalam uji kasus 1 adalah dalam setengah-sel L.Secara teknis, ada sel-T setengah di atas labirin (ketika ada lapisan atas) dan sel setengah B (sepanjang dinding bawah ketika tidak ada lapisan bawah) tetapi mereka tidak terwakili dalam format baru.
Baris atas setengah sel akan dihapus sebagai bagian dari membangun sel penuh di baris yang sama, sehingga setengah sel diwakili dalam format baru sebagai
Setengah R R hanya
|
. Setengah-L memiliki hanyaI
sebagai jalur, hanya penanda keluar dan jalur kosong, atau hanya dinding kosong.Pintu masuk dan keluar
Jika pintu masuk berada di sebelah kiri, kanan atau bawah labirin, maka penanda pintu masuk
I
secara alami akan dimasukkan dalam sel (setengah) sebagai jalur, yang dapat dihilangkan ketika mengembalikan jalur terakhir.Jika pintu masuk berada di atas labirin, langkah pertama (ke bawah) diambil selama fase konstruksi karena sel-T setengah dikeluarkan selama konstruksi. Ini membuat jalur yang bisa diterapkan dalam sel penuh. Dinding atas ditutup setelah itu.
Jika jalan keluar ke kiri, kanan atau bawah labirin, maka
U
secara alami akan dimasukkan dalam sel (setengah). Untuk menghindari keliru sebagai jalur, penanda keluar non-alfanumer&
digunakan sebagai gantiU
. Marker keluar tertanam ke dalam sel atau setengah sel (seperti yang ditentukan di atas).Jika pintu keluar berada di atas labirin, maka itu akan menjadi satu-satunya lubang yang bisa pergi di atas barisan sel teratas (karena pintu masuk, jika ada, sudah akan ditutup). Setiap jalan yang mencapai lubang itu dapat keluar dari labirin dengan mengambil langkah ke atas.
Terakhir, setiap Sel B yang mengandung pintu masuk atau keluar harus menutup dinding kirinya untuk mencegah "penyelesaian" labirin dengan berjalan di sepanjang Sel B. Pintu masuk dan keluar di Sel R atau Sel setengah L tidak perlu diproses lebih lanjut karena algoritma pengisian banjir tidak memungkinkan pergerakan vertikal ke / dari mereka.
Contoh
Sebagai contoh, test case pertama
aku s
dalam format baru. Anda dapat mengonversi labirin lain di sini .
Tahap konstruksi
Fase konstruksi membentuk 13 baris pertama program.
Mengonversi keluar di L Sel setengah untuk keluar dari penanda
Menambahkan dinding di sebelah kiri pintu masuk dan keluar di Sel B
Mengambil langkah pertama jika pintu masuk berada di atas labirin
Melakukan konversi yang sebenarnya
Menutup lubang masuk atas
Hanya menyimpan garis dengan a
1
. Karena labirin memiliki lebar paling sedikit 5 sel dan jumlah kolom terjadi dengan penambahan 3, garis dengan sel format baru harus berisi nomor kolom antara 10 dan 19.Mengonversi keluar di Sel R atau Sel B untuk keluar dari penanda
Isi fase
Fase pengisian membentuk 8 baris berikutnya dari program. Ini menggunakan algoritma pengisian banjir untuk mengisi semua sel dengan jalur terpendek untuk mencapai sana dari pintu masuk.
Letakkan seluruh fase pengisian pada satu lingkaran untuk mengisi seluruh labirin.
Setiap sel dapat bergerak ke kiri melakukannya. Sebuah sel dapat bergerak ke kiri jika
Kemudian, setiap sel dapat bergerak ke kanan melakukannya. Sebuah sel dapat bergerak ke kanan jika
Kemudian, setiap sel dapat bergerak ke bawah melakukannya. Sebuah sel dapat bergerak ke bawah jika
Perhatikan bahwa setengah-sel L tidak dapat bergerak ke bawah karena tidak memiliki nomor kolom.
Kemudian, setiap sel dapat bergerak ke atas melakukannya. Sebuah sel dapat bergerak ke atas jika
Fase kembali
Fase pengembalian membentuk 5 baris terakhir dari program. Fase ini mencari dan mengembalikan jalur yang diisi ke sel keluar.
Pola jalur di pintu keluar tergantung di mana jalan keluarnya:
& <path>
<left wall> <column number> & <path>
<left wall> <column number> · <path>
dan di baris atas.Menemukan sel di baris atas dengan dinding atas yang kosong dan jalur yang tidak kosong. Ini menangani kasus terakhir dengan menambahkan langkah terakhir dan penanda keluar.
Mencocokkan dan mengembalikan jalur yang tidak kosong setelah penanda keluar.
Menghapus penanda keluar dan
I
awalan jalur.sumber
AvKr
? Apakah mereka memiliki arti / apakah mereka singkatan dari atas, bawah, kiri, dan kanan dalam bahasa asli Anda, atau adakah alasan lain mengapa Anda memilih karakter khusus itu?AvKr
merupakan hal yang paling dekat dengan tanda panah dalam alfanumerik.Perl 6 ,
259295 byteBagaimana itu bekerja
Ini meremas labirin sehingga bagian dalam setiap sel adalah 1x1 bukannya karakter ruang 2x1:
Ini adalah fungsi pencarian jalur rekursif. Dibutuhkan tiga parameter: Koordinat saat ini
c=(y,x)
, daftar koordinat yang sudah dikunjungiv
, dan jalur yangp
diambil sejauh ini (sebagai daftar karakter panah).Jika karakter pada koordinat saat ini adalah spasi, maka akan muncul kembali ke empat tetangganya.
Jika karakter pada koordinat saat ini adalah a
I
, karakter akan muncul kembali ke dua tetangga yang tidak "di sepanjang tepi", untuk memaksa solusi melewati labirin dan tidak di sekitarnya.Jika karakter pada koordinat saat ini adalah a
U
, ia memanggiltake
string path terakumulasi.Fungsi rekursif pada awalnya disebut dengan koordinat surat itu
I
, yang ditemukan menggunakan regex.Kata
gather
kunci mengumpulkan semua nilai yangtake
disebut di dalam fungsi, yaitu semua jalur non-siklus yang valid melalui labirin.Jalur terpendek dipilih, setiap panah kedua dijatuhkan untuk menjelaskan fakta bahwa dua gerakan identik diperlukan untuk berpindah dari satu sel ke sel berikutnya, dan panah yang tersisa digabungkan untuk membentuk string yang dikembalikan dari lambda.
sumber
Python 2: 302 byte
Mengambil input sebagai array dari string semua dengan panjang yang sama. Mencetak
0
ke kanan,1
ke bawah,2
ke kiri, dan3
ke atas.Penjelasan
Saya mengambil pendekatan yang berbeda dari jawaban lainnya. Gagasan umum: pencarian secara rekursif dengan menemukan jalur terpendek antara berjalan lurus ke depan dan memutar papan 90 derajat.
Cobalah online!
sumber
I
untuk mencegah jalan keluar dari labirin. Nikmati masa tinggal Anda, dan +1 dari saya. :)JavaScript (ES6), 356 byte
Mengambil input sebagai array karakter 2D. Setiap baris harus diisi dengan satu spasi dan tidak memiliki spasi, di mana pun titik awal / akhir berada.
Menggunakan ide smls tentang memeras labirin untuk membuat setiap sel 1x1 dan menghapus panah berulang dari output.
Tidak Diikat dan Dijelaskan
Cuplikan Tes
Tampilkan cuplikan kode
sumber
Retina , 416 byte
Cobalah online!Seandainya saya melihat pertanyaan ini ketika awalnya dikirim, ini mungkin jawaban yang akan saya berikan, jadi saya tetap mempostingnya, meskipun ada jawaban yang jauh lebih baik di Retina. Penjelasan:
Isi perbatasan. Ini menghindari berjalan di luar labirin (mis. Untuk test case 7).
Tempatkan penanda non-alfabet di pintu masuk.
Banjir mengisi dari pintu keluar ke pintu masuk. Pada setiap langkah, gunakan huruf untuk menunjukkan arah terbaik untuk pergi (WAS - ini mungkin akrab bagi gamer; Saya juga menganggap hjkl tapi saya merasa terlalu membingungkan). Selain itu, lebih suka mengulangi arah yang sama; ini menghindari ke kiri / kanan di antara dua sel yang berdekatan secara vertikal.
Anggaplah langkah pertama turun.
Tetapi jika ada huruf di atas, kiri atau kanan pintu masuk, ubah itu ke langkah pertama.
Pindahkan penanda ke arah langkah terakhir, bacalah arah langkah selanjutnya dari kotak tempat penanda itu bergerak, dan tambahkan itu ke daftar arah. Ini berulang sampai
U
tercapai.Hapus semuanya setelah petunjuk karena tidak diperlukan lagi.
Kotak asli berada pada tata letak 3 × 2. Saat bergerak secara vertikal jika kita zig-zag secara horizontal pengisian banjir akan mengoptimalkan gerakan dan hanya memindahkan karakter 3n-1 secara horizontal, jadi ketika membaginya dengan tiga, kita perlu mengumpulkan. Secara vertikal kami hanya membagi 2.
Saya juga menyelidiki solusi kotak persegi yang benar yaitu di mana matriks karakter itu sendiri persegi daripada menjadi tata letak 3 × 2 dengan batas opsional. Meskipun mungkin tidak sesuai dengan pertanyaan, kemampuan transpos mengurangi jumlah byte menjadi 350: Coba online!
sumber
-
sekitar karakter masuk dan keluar. Karena tantangannya terutama tentang melewati labirin, saya rasa tidak apa-apa, tapi saya ingin tahu: apa masalahnya ketika Anda tidak menempatkan dinding-dinding itu di atas / di bawahI
danU
? Juga, dapatkah Anda memverifikasi ini berfungsi untuk test case 7 denganI
danU
di bagian atas, bukan sisi? TIO melebihi batas 60 detik, jadi saya tidak dapat mengujinya sendiri. Meskipun membaca penjelasan Anda tentang mencoba mencoba turun secara default, saya menganggap itu akan berfungsi dengan baik.