Memasukkan:
Matriks yang berisi bilangan bulat dalam kisaran [0 - 9] .
Tantangan:
Menentukan apakah semua elemen non-nol terhubung satu sama lain secara vertikal dan / atau horizontal.
Keluaran:
Nilai kebenaran jika semua terhubung, dan nilai palsu jika ada elemen / grup bukan nol yang tidak terhubung ke elemen / grup lain.
Kasus uji:
Kasus uji dipisahkan menurut garis. Test case dapat ditemukan dalam format yang lebih nyaman di sini ( Kudos to Dada ).
Yang berikut semuanya terhubung dan harus mengembalikan nilai yang benar:
0
---
0 0
---
1 1 1
0 0 0
---
1 0 0
1 1 1
0 0 1
---
0 0 0 0 0 0
0 0 3 5 1 0
0 1 0 2 0 1
1 1 0 3 1 6
7 2 0 0 3 0
0 8 2 6 2 9
0 0 0 0 0 5
Semua berikut ini tidak terhubung, dan harus mengembalikan nilai falsy:
0 1
1 0
---
1 1 1 0
0 0 0 2
0 0 0 5
---
0 0 5 2
1 2 0 0
5 3 2 1
5 7 3 2
---
1 2 3 0 0 5
1 5 3 0 1 1
9 0 0 4 2 1
9 9 9 0 1 4
0 1 0 1 0 0
Ini adalah kode-golf , jadi pengiriman terpendek di setiap bahasa akan menang. Penjelasan didorong!
Terinspirasi oleh tantangan ini .
code-golf
decision-problem
graph-theory
matrix
Stewie Griffin
sumber
sumber
Jawaban:
Retina 0.8.2 ,
8077 byteCobalah online! Sunting: Disimpan 1 byte berkat @FryAmTheEggman. Penjelasan:
Sederhanakan ke array
@
s dan1
s.Ubah satu
1
menjadi a_
.Isi banjir dari
_
ke yang berdekatan1
s.Uji apakah masih ada yang
1
tersisa.sumber
JavaScript (ES6),
136135 byteMengembalikan boolean.
Uji kasus
Tampilkan cuplikan kode
Berkomentar
Rekursif fungsi g () terlihat pertama untuk sel non-nol (selama bendera global-didefinisikan z diatur ke 0 ) dan kemudian mulai banjir mengisi dari sana (secepat z! = 0 ).
sumber
MATL , 7 byte
Hal ini memberikan matriks yang berisi semua orang sebagai truthy output, atau matriks yang mengandung setidaknya nol sebagai falsy . Cobalah online!
Anda juga dapat memverifikasi kebenaran / kepalsuan menambahkan cabang
if
-else
di footer; coba juga!Atau verifikasi semua kasus uji .
Penjelasan
sumber
Bahasa Wolfram (Mathematica) , 54 byte
Disimpan 2 byte berkat pengguna202729.
Cobalah online!
sumber
C, 163 byte
Terima kasih kepada @ user202729 untuk menghemat dua byte!
Loop melalui matriks sampai menemukan elemen non-nol pertama. Kemudian hentikan perulangan untuk sementara waktu dan secara rekursif mengatur setiap elemen non-nol yang terhubung ke elemen yang ditemukan menjadi nol. Kemudian loop melalui sisa matriks memeriksa apakah setiap elemen sekarang nol.
Cobalah online!
Belum dibuka:
sumber
Perl,
8079787370 byteTermasuk
+2
untuk0a
Berikan matriks input tanpa spasi pada STDIN (atau sebenarnya sebagai baris yang dipisahkan oleh spasi putih apa pun)
Lebih mudah dibaca jika dimasukkan ke dalam file:
sumber
Java 8, 226 byte
Ini butuh waktu cukup lama, jadi saya senang itu berfungsi sekarang ..
Penjelasan:
Cobalah online.
sumber
APL (Dyalog Unicode) , 36 byte SBCS
Cobalah online!
sumber
Jelly , 23 byte
Cobalah online!
Penjelasan.
Program memberi label pada masing-masing komponen morfologis dengan angka yang berbeda, lalu periksa apakah jumlahnya kurang dari 3. (termasuk
0
).Pertimbangkan baris dalam matriks.
Terapkan fungsi ini berulang kali untuk semua baris dan kolom dalam matriks, dalam semua pesanan, akhirnya semua komponen morfologi akan memiliki label yang sama.
Dan akhirnya...
sumber
¦
butuh O (n).Haskell , 132 byte
diekstraksi dari Memecahkan Teka-teki Hitori
indices m
daftar(line,cell)
lokasi kisi masukan.filter((/=0).(m!))
memfilter semua lokasi dengan nilai bukan nol.splitAt 1
partisi dari anggota pertama menjadi daftar tunggal di sebelah daftar lainnya.any(==1)[(b-d)^2+(p-q)^2|(d,q)<-f]
memberitahu jika(b,p)
menyentuh perbatasanf
.\(f,e)->partition(\(b,p)->touches(b,p)f)e
memisahkan para touchers dari yang belum [touchers].until(null.fst)advanceFrontier
ulangi ini sampai perbatasan tidak bisa maju lebih jauh.null.snd
melihat pada hasil apakah semua lokasi yang ingin dicapai memang tercapai.Cobalah online!
sumber
Grime , 37 byte
Mencetak
1
untuk pertandingan dan0
tanpa pertandingan. Cobalah online!Penjelasan
Nonterminal
C
cocok dengan karakter bukan nol yang terhubung ke karakter bukan nol pertama dari matriks dalam urutan pembacaan bahasa Inggris.Beberapa penjelasan:
e
cocok dengan persegi panjang nol lebar atau tinggi yang merupakan bagian dari tepi matriks input, dan$
merupakan "wildcard" yang cocok dengan apa pun. Ekspresie/\0{/e\0*0$e
dapat divisualisasikan sebagai berikut:Ekspresi
CoX^0oX
sebenarnya diuraikan sebagai((CoF)0)oX
; yangoF
danoX
adalah operator postfix dan gabungan dari token sarana Rangkaian horizontal. The^
memberikan penjajaran prioritas lebih tinggi kemudianoX
, sehingga rotasi yang diterapkan pada seluruh sub-ekspresi. TheoF
mengoreksi orientasiC
setelah diputar olehoX
; jika tidak, bisa cocok dengan koordinat nol pertama dalam urutan pembacaan bahasa Inggris yang diputar.Ini berarti bahwa semua karakter bukan nol harus terhubung dengan yang pertama. Grid specifier
:
secara teknis adalah operator postfix, tetapiC|:\0
merupakan sintaksis untuk(C|\0):
.sumber
Perl 5 ,
131129 + 2 (-ap
) = 133 byteCobalah online!
sumber
Python 2 ,
211163150 byteCobalah online!
Output melalui kode keluar. Input adalah sebagai daftar 1d dan lebar matriks.
sumber