pengantar
Ada sebuah desa kecil dengan hanya beberapa rumah dan ladang kosong. Para birokrat lokal ingin membagi desa menjadi banyak sehingga setiap lot mengandung tepat satu rumah, dan batas-batas tanah membentuk garis lurus yang bagus. Tugas Anda adalah menentukan apakah ini mungkin.
Tugas
Input Anda adalah array 2D persegi panjang dari bit; 1 mewakili rumah dan 0 bidang kosong. Ukurannya akan minimal 1 × 1 , dan itu akan mengandung setidaknya satu 1. Anda dapat mengambil input dalam format yang masuk akal (daftar bilangan bulat bersarang, daftar string, string multiline, dll.).
Program Anda harus menentukan apakah array dapat dibagi menjadi sel-sel kisi menggunakan garis lurus dan vertikal lurus sehingga setiap sel kisi mengandung tepat satu 1. Sel-sel kisi mungkin memiliki ukuran dan bentuk yang berbeda, meskipun mereka selalu berbentuk persegi panjang. Garis harus berjalan dari satu tepi array ke tepi yang berlawanan.
Misalnya, berikut ini adalah pembagian array yang valid:
00|0010|01|1
01|0000|00|0
--+----+--+-
00|0000|00|1
01|0010|01|0
--+----+--+-
01|1000|10|1
sedangkan pembagian berikut ini tidak valid, karena ada sel-sel jaringan tanpa 1s atau lebih dari satu 1:
00|0010|01|1
--+----+--+-
01|0000|00|0
00|0000|00|1
01|0010|01|0
--+----+--+-
00|1000|10|1
Jika ada pembagian yang valid, Anda harus menampilkan nilai kebenaran, dan jika tidak, nilai palsu.
Aturan dan penilaian
Anda dapat menulis program atau fungsi lengkap. Hitungan byte terendah menang.
Uji kasus
[[1]] -> True
[[0,1],[1,0]] -> True
[[1,1],[1,0]] -> False
[[1,0,1],[0,1,0]] -> True
[[1,0],[0,1],[0,1]] -> True
[[1,0,0],[0,0,1],[0,1,1]] -> True
[[1,1,1],[1,1,1],[1,1,1]] -> True
[[1,0,1],[0,1,0],[1,0,0]] -> True
[[1,0,0],[1,0,0],[0,1,1]] -> False
[[0,0,0,0,1],[1,0,0,1,0],[0,0,0,1,0]] -> False
[[0,0,1,0,1],[0,0,0,1,0],[0,0,0,0,0]] -> True
[[1,1,0,0,0],[0,0,0,0,0],[1,0,1,0,0]] -> True
[[1,1,0,1,1],[0,1,0,1,1],[1,0,0,0,0]] -> True
[[0,0,0,0,0,0,0],[0,1,1,1,0,1,0],[0,1,0,0,1,0,0],[0,0,0,0,0,0,1],[0,0,1,0,0,0,1],[1,1,0,1,1,0,0]] -> False
[[1,1,0,0,0,0,0],[1,0,1,1,0,1,0],[0,0,0,0,1,0,0],[0,1,0,1,1,0,0],[1,0,0,0,1,1,0],[0,0,0,0,0,1,0]] -> False
[[0,1,0,1,1,1,0],[0,0,0,0,1,0,0],[0,0,0,0,0,0,0],[1,0,0,1,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,1]] -> True
[[0,1,0,0,1,0,1],[1,0,0,0,1,0,1],[0,0,1,0,1,0,1],[1,0,0,0,1,1,0],[0,0,0,1,1,1,0],[0,1,0,0,1,0,1]] -> True
[[0,1,0,0,1,0,0,1,0],[0,0,0,0,1,1,0,1,0],[1,1,0,0,1,0,0,0,0],[0,0,1,0,1,0,1,0,0],[0,0,1,0,1,0,1,0,0],[0,1,0,0,0,1,0,0,1],[0,1,0,0,0,0,1,0,0]] -> False
[[1,0,1,0,0,1,1,0,1],[0,1,1,0,0,1,1,0,1],[1,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,1,0,0,0,0,1,1],[0,1,1,0,1,0,1,0,1],[1,0,1,0,0,1,1,0,1]] -> True
[[1, 0, 1], [0, 1, 0], [1, 0, 0]]
Itu adalah satu-satunya matriks 3x3 yang gagal untuk pendekatan baru saya.Jawaban:
Pyth,
3029262423 byteCobalah online.
Saya yakin ini akan menjadi lebih pendek. Ini adalah O (2 mn ) , di mana m dan n adalah lebar dan tinggi array, tetapi menyelesaikan dua test case terakhir dalam 45 detik pada laptop saya dengan baterai (i5-5200U dengan kinerja terbatas).
Menghasilkan jumlah solusi.
Penjelasan
Array lima dimensi benar-benar menyenangkan untuk dikerjakan. </sarcasm> Anda tidak seharusnya memahami bagaimana ini bekerja bahkan dengan penjelasannya.
sumber
Jeli , 22 byte
Cobalah online!
sumber
Haskell , 116 byte
Cobalah online!
sumber
mergerows
menjadim
.[[1,0],[0,1],[1,0]]
. Masalahnya adalah bahwa keruntuhan serakah dapat menghalangi keruntuhan yang lebih baik di kemudian hari.[[1,1],[1,0]]
keruntuhan saya salah menghalangi[[1],[1],[1]]
solusi. Biarkan saya tidur lebih dari ini atau harus saya hapus?Jelly , 20 byte
Ini masih merupakan solusi brute-force, tapi ini sedikit lebih cepat daripada jawaban saya yang lain - yang tidak dapat mengatasi dua kasus uji terakhir pada TIO - dan menangani semua kasus uji dalam ~ 4 detik.
Cobalah online!
Bagaimana itu bekerja
sumber