Aturan:
Dalam permainan ini Anda mulai di bagian atas kotak persegi panjang ukuran N x M yang terdiri dari dinding dan ruang terbuka. Input adalah N baris karakter M, di mana .
menentukan ruang terbuka dan x
menentukan dinding. Program Anda harus menampilkan angka K terkecil sehingga terdapat jalur dari sudut kiri atas ke sudut kanan bawah (tanpa diagonal) yang melintasi dinding K.
Misalnya, diberi input:
..x..
..x..
xxxxx
..x..
..x..
output program Anda 2
.
Contoh lain:
keluaran 4
:
xxxxx
x.x.x
x.x.x
x..xx
keluaran 0
:
.xxxxxxxx
.x...x...
.x.x.x.x.
.x.x...x.
...xxxxx.
keluaran 6
:
xx
xx
xx
xx
xx
Berita tambahan:
Jika itu membuat hidup Anda lebih mudah, Anda dapat menentukan N dan M sebagai parameter baris perintah.
Kredit ekstra jika Anda dapat membuat program Anda mencetak jalur dalam beberapa bentuk atau lainnya.
Jawaban:
Ruby 1.9
(235)(225)(222)(214)Saya tidak tahu apakah ini lebih pendek dari program yang didasarkan pada Dijkstra, tetapi saya pikir saya akan mencoba pendekatan yang berbeda. Ini menggunakan regex dalam satu lingkaran untuk menandai setiap ruang dengan jumlah minimal dinding yang diperlukan untuk mencapainya.
Input ditentukan sebagai file pada baris perintah, yaitu
Tidak Disatukan:
sumber
Perl 5.10 (164)
Sangat mirip dengan solusi migimaru, hanya dengan sentuhan Perl ekstra. 5.10 diperlukan untuk
\K
masuks///
.sumber
Python
406378360348418 karakterDijkstra Sederhana, karena bergerak dengan berat berada di
x
lapangan. Hal ini dilakukan dalam "gelombang", loop pertama dengan menemukan.
bidang yang menyentuh depan dan mengaturnya pada berat yang sama, daripada sekali menemukanx
bidang yang menyentuh depan dan mengaturnya pada+1
berat. Ulangi sementara tidak ada lagi bidang yang belum dikunjungi.Pada akhirnya kita tahu berat untuk setiap bidang.
Input ditentukan sebagai file pada baris perintah:
Perbarui: mencetak jalur.
sumber
Versi C ++ (
610607606584)Menerapkan algoritma Dijkstra.
Tidak golf:
sumber