Intro terkait anak-anak
Setiap kali saya membawa anak-anak saya ke taman hiburan, anak-anak menjadi semakin gugup semakin dekat kita ke taman, dengan puncak keberanian ketika kita berada di tempat parkir dan tidak menemukan tempat untuk parkir. Jadi saya telah memutuskan saya perlu metode untuk menemukan tempat parkir gratis terdekat untuk meminimalkan waktu yang dihabiskan parkir.
Pendahuluan teknis
Bayangkan representasi dari tempat parkir seperti ini:
*****************
* *
* ··CC··C··CC·· *
* ************* *
* ··CCCCCCCCC·· *
* *
**********E******
Dalam representasi ini *
berarti dinding, tempat ·
parkir gratis, E
titik masuk dan C
mobil yang sudah diparkir. Setiap spasi putih adalah posisi yang bisa diparkir mobil untuk bergerak di sekitar tempat parkir. Sekarang mari kita memperluas konsep ini ke 3D untuk membuat tempat parkir multi-level:
1st floor 2nd floor 3rd floor 4th floor
***************** ***************** ***************** *****************
* 1 * 2 * 3 * *
* CCCCCCCCCCCCC * * CCCCCCCCCCCCC * * ····C··CCCCCC * * ······C······ *
* ************* * * ************* * * ************* * * ************* *
* CCCCCCCCCCCCC * * CCCCCCCCCCCCC * * ···CCCCCCCCCC * * ··C·······C·· *
* * * 1 * 2 * 3
**********E****** ***************** ***************** *****************
Angka-angka 1
, 2
dan 3
mewakili koneksi antar level. The 1
dari menghubungkan lantai pertama dengan 1
di lantai jadi loncatan mobil ke 1
posisi di lantai pertama muncul dalam 1
posisi di lantai dua.
Tantangan
Memberikan skema tempat parkir seperti yang ditunjukkan sebelumnya, tulis program terpendek yang menghitung jarak ke tempat parkir gratis terdekat, sesuai dengan yang berikut
Aturan
- Input akan berupa array char 3D atau array string 2D atau yang setara, dan output akan berupa integer tunggal yang mewakili jumlah langkah yang harus diambil mobil untuk sampai ke tempat parkir gratis terdekat. Jika Anda menerima array karakter 3D, indeks pertama mungkin mewakili nomor lantai dan indeks kedua dan ketiga menunjukkan posisi (x, y) untuk setiap lantai, tetapi ini tergantung pada Anda.
- Tidak akan ada lebih dari 9 landai, diwakili oleh
[1-9]
. - Mobil mulai dari
E
posisi (hanya akan ada satu titik masuk per peta) dan bergerak menggunakan spasi putih di salah satu dari empat arah setiap kali: atas, bawah, kiri, kanan. Mobil juga dapat masuk ke·
posisi dan[1-9]
posisi. - Setiap perubahan posisi (langkah) dihitung sebagai 1, dan setiap kali mobil melaju dari satu lantai ke lantai lain dihitung sebagai 3 saat mobil harus menanjak. Dalam hal ini, gerakan dari spasi putih di samping a
1
ke1
dirinya sendiri adalah yang dihitung sebagai 3 langkah, karena sebagai hasil dari gerakan ini, mobil muncul di1
posisi di lantai lain. - Mobil tidak bisa melampaui batas matriks.
- Hitungan akan berakhir ketika mobil yang akan diparkir berada di posisi yang sama dengan a
·
. Jika tidak ada ruang parkir gratis yang dapat dijangkau, Anda dapat mengembalikan nol, bilangan bulat negatif, nilai nol, atau kesalahan.
Contohnya
Pada contoh di atas hasilnya akan menjadi 32, karena lebih murah untuk pergi ke lantai empat dan parkir di tempat parkir terdekat di dekat 3
. Ruang parkir gratis terdekat di lantai tiga berjarak 33 dan 34.
Contoh lain:
1st floor 2nd floor 3rd floor 4th floor
***************** ***************** ***************** *****************
* 1 * 2 * 3 * *
* CCCCCCCCCCCCC * * CCCCCCCCCCCCC * * ····C··CCCCCC * * ······C······ *
* ************* * * ************* * * ************* * * ************* *
* CCCCCCCCCCCCC * * ·CCCCCCCCCCCC * * ···CCCCCCCCCC * * ··C·······C·· *
* * * 1 * 2 * 3
**********E****** ***************** ***************** *****************
Answer: 28 (now the parking space in the 2nd floor is closer)
1st floor 2nd floor 3rd floor 4th floor
***************** ***************** ***************** *****************
* 1 4 2 5 3 6 *
* CCCCCCCCCCCCC * * CCCCCCCCCCCCC * * ····C··CCCCCC * * ······C······ *
* ************* * * ************* * * ************* * * ************* *
* CCCCCCCCCCCCC * * CCCCCCCCCCCCC * * ···CCCCCCCCCC * * ··C·······C·· *
4 * 5 1 6 2 * 3
**********E****** ***************** ***************** *****************
Answer: 24 (now it's better to go to ramp 4 and then to ramp 5 to the third floor)
1st floor 2nd floor 3rd floor 4th floor
***************** ***************** ***************** *****************
* 1 * * * 3 * 2
* CCCCCCCCCCCCC * * CCCCCCCCCCCCC * * ····C··CCCCCC * * ······C······ *
* ************* * * ************* * * ************* * * ************* *
* CCCCCCCCCCCCC * * ·CCCCCCCCCCCC * * ···CCCCCCCCCC * * ··C·······C·· *
* * * 3 * 2 * 1
**********E****** ***************** ***************** *****************
Answer: 16 (now the parking space in the 4th floor is closer)
1st floor 2nd floor 3rd floor 4th floor 5th floor
************ ************ ************ ************ ************
*CCCCCCCCC 1 *CCCCCCCCC 2 *CCCCCCCCC 3 *·CCCCCCCC 4 *········C *
* * * * * * * * * *
*CCCCCCCCC E *CCCCCCCCC 1 *CCCCCCCCC 2 *··CCCCCCC 3 *·······CC 4
************ ************ ************ ************ ************
Answer: 29 (both the nearest parking spaces at the 4th and 5th floors are at the same distance)
1st floor 2nd floor 3rd floor
************ ************ ************
*CCCCCCCCC 1 *CCCCCCCCC 2 *CCCCCCCCC *
* * * * * *
*CCCCCCCCC E *CCCCCCCCC 1 *CCCCCCCCC 2
************ ************ ************
Answer: -1 (no free parking space)
1st floor
************
* *
* *
* E*
************
Answer: -1 (no parking space at all)
1st floor
************
* ····· *
*· ****
* ····· * E
*********
Answer: -1 (the parking lot designer was a genius)
Alternatif
- Anda dapat menggunakan karakter apa pun yang Anda inginkan untuk mewakili peta tempat parkir, cukup tentukan dalam jawaban Anda yang merupakan karakter yang Anda pilih dan apa artinya.
Ini adalah kode-golf , jadi semoga program / metode / lambda / tersingkat apa pun untuk setiap bahasa menang!
Jika Anda memerlukan bantuan dengan algoritme, silakan periksa implementasi (tidak di-unign) saya di C # .
Jawaban:
JavaScript (ES6), 199 byte
Cobalah online!
Bagaimana?
Fungsi rekursif g () mengambil sebagai input:
Jika f didefinisikan, kita cukup menyalinnya ke lantai F saat ini . Kalau tidak, kita perlu mencari lantai baru dan koordinat baru dengan mengulangi setiap lantai dan setiap baris sampai kita menemukan titik masuk c :
Kami mendefinisikan r sebagai baris saat ini di lantai saat ini:
Langkah selanjutnya adalah memastikan bahwa sel saat ini c at (x, y) didefinisikan:
Jika ya, kami menandainya sebagai dikunjungi dengan menyetelnya ke g , nilai yang tidak memicu salah satu tes yang akan datang:
Jika c adalah tempat parkir gratis, kami menghentikan rekursi. Dan jika jumlah total gerakan lebih rendah dari skor terbaik kami sebelumnya, kami memperbarui m sesuai:
Jika kami baru saja mencapai lantai baru ( f tidak ditentukan ) atau c adalah spasi, kami memproses panggilan rekursif untuk setiap sel di sekitarnya:
Kalau tidak, jika c adalah penanda ramp (yaitu digit bukan nol), kami memproses satu panggilan rekursif untuk mencapai lantai baru:
Akhirnya, kami mengembalikan sel saat ini ke nilai awalnya sehingga dapat dikunjungi lagi di jalur rekursi lainnya:
sumber
Kotlin , 768 byte
periode yang digunakan. dari pada ·. Seandainya saya mengerti jawaban Arnauld karena kehilangan 500 byte akan menyenangkan.
Cobalah online!
sumber
Powershell,
299292 byteDiasumsikan bahwa peta itu persegi panjang .
Ia menggunakan
x
sebagai gantinya·
. Untuk mendapatkan·
, Anda perlu untuk menyimpan naskah sebagai ASCII (tidak UTF-8) dan menggantix
pada·
.Skrip yang tidak disatukan dan uji:
Keluaran:
Output yang diperluas untuk parkir dengan 16 langkah:
Penjelasan
Ini semacam algoritma pathfinding Lee . Hanya satu hal yang cerdas: 3 langkah di jalan direalisasikan sebagai negara tiruan
H->G->F->E
Powershell untuk desainer parkir jenius,
377369 byteDesain parkir adalah
2D string array
. Tidak ada asumsi tentang peta: string panjang apa pun, lantai tanpa dinding, parkir tanpa titik masuk, jalan landai multi-lantai dan multi. Biaya genus adalah + 26%.Skrip yang tidak disatukan dan uji:
sumber