Bayangkan kita memiliki matriks bit (yang mengandung setidaknya satu 1
):
0 1 0 1 1 0 1 0 0 1 0
0 1 0 1 0 0 1 0 1 1 0
0 0 1 0 1 1 0 1 0 1 0
1 1 0 0 1 0 0 1 1 0 1
0 0 0 1 0 1 1 0 0 1 0
Kami ingin mengatur beberapa bit dalam matriks ini sehingga membentuk gumpalan berdekatan 1
, di mana setiap bit 1
terhubung secara langsung atau tidak langsung satu sama lain 1
melalui gerakan ortogonal:
0 1 1 1 1 1 1 0 0 1 0
0 1 0 1 0 0 1 0 1 1 0
0 1 1 0 1 1 1 1 0 1 0
1 1 0 0 1 0 0 1 1 1 1
0 0 0 1 1 1 1 0 0 1 0
(Anda dapat melihat ini lebih jelas dengan menelusuri 1
dengan fitur "temukan" di browser Anda.)
Namun, kami juga ingin meminimalkan jumlah bit yang kami atur.
Tugas
Diberikan matriks (atau array array) bit atau boolean, kembalikan jumlah minimum bit yang perlu diatur untuk membuat benua bersebelahan dari 1
s. Seharusnya dimungkinkan untuk berpindah dari satu set bit ke dalam matriks ke yang lain dengan hanya melakukan perjalanan dalam arah ortogonal ke bit set lainnya.
Ini adalah kode-golf , sehingga pengiriman terpendek yang valid (diukur dalam byte) menang.
Uji Kasus
0 1 0 1 1 0 1 0 0 1 0
0 1 0 1 0 0 1 0 1 1 0
0 0 1 0 1 1 0 1 0 1 0
1 1 0 0 1 0 0 1 1 0 1
0 0 0 1 0 1 1 0 0 1 0
=> 6
1 0 0 0 0 0 1 0 0
1 1 0 0 1 1 1 0 0
1 1 1 0 1 1 1 1 1
0 1 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1
0 1 0 0 0 0 1 1 0
1 0 0 0 0 0 1 0 0
=> 4
0 0 0 1 1 1 0 1 1
0 0 1 0 0 0 0 1 0
0 0 1 1 1 1 1 1 0
1 1 0 0 1 1 0 0 0
0 0 1 1 1 0 0 1 1
0 1 1 1 0 0 0 0 0
1 1 1 0 0 1 1 1 0
1 1 1 0 1 1 0 1 1
0 0 0 0 1 0 0 0 1
1 1 0 0 1 1 0 1 1
0 0 0 0 0 0 0 1 0
0 1 1 1 1 0 0 0 0
0 0 0 1 1 0 0 0 1
0 1 0 0 1 0 1 1 0
0 1 1 1 0 0 0 0 1
=> 8
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
=> 0
sumber
1
dalam matriks?Jawaban:
C (gcc),
308306 byteFungsi
f
menerima(height, width, flattened array, pointer to ans)
, dan mengembalikan jawaban dengan pointer.Jika tidak ada
1
dalam matriks, itu akan kembali0
.Cobalah online!
Tidak Disatukan:
sumber
Python 2 , 611 byte
Program lengkap yang mengambil daftar daftar melalui input pengguna. Fungsi
I
dand
menghitung jumlah pulau dalam array. Perulangan for pada bagian akhir menyebutkan semua kemungkinan di mana Anda dapat mengubah0
s ke1
s lalu jika ada satu pulau tersisa, jumlah1
s ditambahkan ke daftarC
. Minimum dari daftar itu adalah jumlah minimum bit bit yang diperlukan untuk menghubungkan setiap pulau. Ini adalah algoritma yang sangat lambat sehingga tidak menjalankan test case yang diberikan di bawah 60an (saya tidak mencoba lagi) tetapi saya mencoba beberapa test case yang lebih kecil (~ 5x5) dan sepertinya berfungsi dengan benar. Saya mendapatkan algoritma penghitungan pulau dari halaman ini .Cobalah online!
Versi pregolf sebelum saya mengoptimalkan beberapa hal:
sumber