Periksa apakah semua elemen non-nol dalam matriks terhubung

19

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 , jadi pengiriman terpendek di setiap bahasa akan menang. Penjelasan didorong!


Terinspirasi oleh tantangan ini .

Stewie Griffin
sumber
Mungkin input harus berisi hanya satu dan nol (atau kebenaran dan kesalahan), karena ini pada dasarnya tentang komponen yang terhubung.
NikoNyrh
Bisakah kita mengambil input sebagai array 1d dan sejumlah kolom?
Ovs
@saya yakin. Saya tidak bisa melihat bahwa itu akan memberi Anda keuntungan lebih dari orang lain yang sudah menjawab.
Stewie Griffin
2
Terkait : berapa banyak nol yang perlu Anda ubah untuk membuat semua elemen bukan nol terhubung
dylnan
Terkait : hitung jumlah komponen (tetapi dengan entri diagonal yang berdekatan).
Misha Lavrov

Jawaban:

9

Retina 0.8.2 , 80 77 byte

T`d`@1
1`1
_
+m`^((.)*)(1|_)( |.*¶(?<-2>.)*(?(2)(?!)))(?!\3)[1_]
$1_$4_
^\D+$

Cobalah online! Sunting: Disimpan 1 byte berkat @FryAmTheEggman. Penjelasan:

T`d`@1

Sederhanakan ke array @s dan 1s.

1`1
_

Ubah satu 1menjadi a _.

+m`^((.)*)(1|_)( |.*¶(?<-2>.)*(?(2)(?!)))(?!\3)[1_]
$1_$4_

Isi banjir dari _ke yang berdekatan 1s.

^\D+$

Uji apakah masih ada yang 1tersisa.

Neil
sumber
@FryAmTheEggman Terima kasih, dan Anda memberi saya ide bagaimana cara menyimpan dua byte lagi juga!
Neil
7

JavaScript (ES6), 136 135 byte

Mengembalikan boolean.

m=>!/[1-9]/.test((g=(y,x=0)=>1/(n=(m[y]||0)[x])&&!z|n?(m[y++][x]=0,z=n)?g(y,x)&g(--y-1,x)&g(y,x+1)||g(y,x-1):g(m[y]?y:+!++x,x):m)(z=0))

Uji kasus

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 ).

m =>                               // given the input matrix m
  !/[1-9]/.test((                  // test whether there's still a non-zero digit
    g = (y, x = 0) =>              //   after recursive calls to g(), starting at (x=0,y=0):
      1 / (n = (m[y] || 0)[x]) &&  //     n = current cell; if it is defined:
      !z | n ? (                   //       if z is zero or n is non-zero:
          m[y++][x] = 0,           //         we set the current cell to zero
          z = n                    //         we set z to the current cell
        ) ?                        //         if z is non-zero:
          g(y, x) &                //           flood-fill towards bottom
          g(--y - 1, x) &          //           flood-fill towards top
          g(y, x + 1) ||           //           flood-fill towards right
          g(y, x - 1)              //           flood-fill towards left
        :                          //         else:
          g(m[y] ? y : +!++x, x)   //           look for a non-zero cell to start from
      :                            //       else:
        m                          //         return the matrix
    )(z = 0)                       //   initial call to g() + initialization of z
  )                                // end of test()
Arnauld
sumber
7

MATL , 7 byte

4&1ZI2<

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- elsedi footer; coba juga!

Atau verifikasi semua kasus uji .

Penjelasan

4       % Push 4 (defines neighbourhood)
&       % Alternative input/output specification for next function
1ZI     % bwlabeln with 2 input arguments: first is a matrix (implicit input),
        % second is a number (4). Nonzeros in the matrix are interpreted as
        % "active" pixels. The function gives a matrix of the same size
        % containing positive integer labels for the connected components in 
        % the input, considering 4-connectedness
2<      % Is each entry less than 2? (That would mean there is only one
        % connected component). Implicit display
Luis Mendo
sumber
1
Catatan OP: kalau-kalau ada keraguan: outputnya baik-baik saja dan mematuhi meta post yang ditautkan.
Stewie Griffin
Ini mengejutkan saya bahwa MATL / matlab menganggap array angka sebagai IFF yang sebenarnya tidak mengandung nol. mathworks.com/help/matlab/ref/if.html (komentar sebelumnya dihapus)
Sparr
@Parr (Sebenarnya, benar IFF tidak mengandung angka nol dan tidak kosong .) Saya juga bingung ketika saya belajar bahwa setiap array yang tak kosong adalah truthy dalam bahasa lain
Luis Mendo
4

C, 163 byte

Terima kasih kepada @ user202729 untuk menghemat dua byte!

*A,N,M;g(j){j>=0&j<N*M&&A[j]?A[j]=0,g(j+N),g(j%N?j-1:0),g(j-N),g(++j%N?j:0):0;}f(a,r,c)int*a;{A=a;N=c;M=r;for(c=r=a=0;c<N*M;A[c++]&&++r)A[c]&&!a++&&g(c);return!r;}

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:

*A, N, M;

g(j)
{
    j>=0 & j<N*M && A[j] ? A[j]=0, g(j+N), g(j%N ? j-1 : 0), g(j-N), g(++j%N ? j : 0) : 0;
}

f(a, r, c) int*a;
{
    A = a;
    N = c;
    M = r;

    for (c=r=a=0; c<N*M; A[c++] && ++r)
        A[c] && !a++ && g(c);

    return !r;
}
Steadybox
sumber
2

Perl, 80 79 78 73 70 byte

Termasuk +2untuk0a

Berikan matriks input tanpa spasi pada STDIN (atau sebenarnya sebagai baris yang dipisahkan oleh spasi putih apa pun)

perl -0aE 's%.%$".join"",map chop,@F%seg;s%\b}|/%z%;y%w-z,-9%v-~/%?redo:say!/}/'
000000
003510
010201
110316
720030
082629
000005
^D

Lebih mudah dibaca jika dimasukkan ke dalam file:

#!/usr/bin/perl -0a
use 5.10.0;
s%.%$".join"",map chop,@F%seg;s%\b}|/%z%;y%w-z,-9%v-~/%?redo:say!/}/
Ton Hospel
sumber
1

Java 8, 226 byte

m->{int c=0,i=m.length,j;for(;i-->0;)for(j=m[i].length;j-->0;)if(m[i][j]>0){c++;f(m,i,j);}return c<2;}void f(int[][]m,int x,int y){try{if(m[x][y]>0){m[x][y]=0;f(m,x+1,y);f(m,x,y+1);f(m,x-1,y);f(m,x,y-1);}}catch(Exception e){}}

Ini butuh waktu cukup lama, jadi saya senang itu berfungsi sekarang ..

Penjelasan:

Cobalah online.

m->{                   // Method with integer-matrix parameter and boolean return-type
  int c=0,             //  Amount of non-zero islands, starting at 0
      i=m.length,j;    //  Index integers
  for(;i-->0;)         //  Loop over the rows
    for(j=m[i].length;j-->0;)
                       //   Inner loop over the columns
      if(m[i][j]>0){   //    If the current cell is not 0:
        c++;           //     Increase the non-zero island counter by 1
        f(m,i,j);}     //     Separate method call to flood-fill the matrix
  return c<2;}         //  Return true if 0 or 1 islands are found, false otherwise

void f(int[][]m,int x,int y){
                        // Separated method with matrix and cell input and no return-type
  try{if(m[x][y]>0){    //  If the current cell is not 0:
    m[x][y]=0;          //   Set it to 0
    f(m,x+1,y);         //   Recursive call south
    f(m,x,y+1);         //   Recursive call east
    f(m,x-1,y);         //   Recursive call north
    f(m,x,y-1);}        //   Recursive call west
  }catch(Exception e){}}//  Catch and swallow any ArrayIndexOutOfBoundsExceptions
                        //  (shorter than manual if-checks)
Kevin Cruijssen
sumber
1

Jelly , 23 byte

FJṁa@µ«Ḋoµ€ZUµ4¡ÐLFQL<3

Cobalah online!


Penjelasan.

Program memberi label pada masing-masing komponen morfologis dengan angka yang berbeda, lalu periksa apakah jumlahnya kurang dari 3. (termasuk0 ).

Pertimbangkan baris dalam matriks.

«Ḋo   Given [1,2,3,0,3,2,1], return [1,2,3,0,2,1,1].
«     Minimize this list (element-wise) and...
 Ḋ      its dequeue. (remove the first element)
      So min([1,2,3,0,3,2,1],
             [2,3,0,3,2,1]    (deque)
      ) =    [1,2,0,0,2,1,1].
  o   Logical or - if the current value is 0, get the value in the input.
         [1,2,0,0,2,1,1] (value)
      or [1,2,3,0,3,2,1] (input)
      =  [1,2,3,0,2,1,1]

Terapkan fungsi ini berulang kali untuk semua baris dan kolom dalam matriks, dalam semua pesanan, akhirnya semua komponen morfologi akan memiliki label yang sama.

µ«Ḋoµ€ZUµ4¡ÐL  Given a matrix with all distinct elements (except 0),
               label two nonzero numbers the same if and only if they are in
               the same morphological component.
µ«Ḋoµ          Apply the function above...
     €           for ach row in the matrix.

      Z        Zip, transpose the matrix.
       U       Upend, reverse all rows in the matrix.
               Together, ZU rotates the matrix 90° clockwise.
         4¡    Repeat 4 times. (after rotating 90° 4 times the matrix is in the
               original orientation)
           ÐL  Repeat until fixed.

Dan akhirnya...

FJṁa@ ... FQL<3   Main link.
F                 Flatten.
 J                Indices. Get `[1,2,3,4,...]`
  ṁ               old (reshape) the array of indices to have the same
                  shape as the input.
   a@             Logical AND, with the order swapped. The zeroes in the input
                  mask out the array of indices.
      ...         Do whatever I described above.
          F       Flatten again.
           Q      uniQue the list.
            L     the list of unique elements have Length...
             <3   less than 3.
pengguna202729
sumber
Karunia imajiner jika Anda bisa melakukannya dalam waktu linier. Saya pikir itu tidak mungkin di Jelly, bahkan ¦butuh O (n).
user202729
(tanpa Python eval, tentu saja)
user202729
1

Haskell , 132 byte

 \m->null.snd.until(null.fst)(\(f,e)->partition(\(b,p)->any(==1)[(b-d)^2+(p-q)^2|(d,q)<-f])e).splitAt 1.filter((/=0).(m!)).indices$m

diekstraksi dari Memecahkan Teka-teki Hitori

indices mdaftar (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 perbatasan f.

\(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!

Roman Czyborra
sumber
1

Grime , 37 byte

C=[,0]&<e/\0{/e\0*0$e|CoF^0oX
e`C|:\0

Mencetak 1untuk pertandingan dan 0tanpa pertandingan. Cobalah online!

Penjelasan

Nonterminal Ccocok dengan karakter bukan nol yang terhubung ke karakter bukan nol pertama dari matriks dalam urutan pembacaan bahasa Inggris.

C=[,0]&<e/\0{/e\0*0$e|CoF^0oX
C=                             A rectangle R matches C if
  [,0]                         it is a single character other than 0
      &                        and
       <                       it is contained in a rectangle S which matches this pattern:
        e/\0{/e\0*0$e           R is the first nonzero character in the matrix:
        e                        S has an edge of the matrix over its top row,
         /0{/                    below that a rectangle of 0s, below that
             e\0*0$e             a row containing an edge, then any number of 0s,
                                 then R (the unescaped 0), then anything, then an edge.
                    |CoF^0oX    or R is next to another match of C:
                     CoF         S is a match of C (with fixed orientation)
                        ^0       followed by R,
                          oX     possibly rotated by any multiple of 90 dergees.

Beberapa penjelasan: ecocok dengan persegi panjang nol lebar atau tinggi yang merupakan bagian dari tepi matriks input, dan $merupakan "wildcard" yang cocok dengan apa pun. Ekspresi e/\0{/e\0*0$edapat divisualisasikan sebagai berikut:

+-e-e-e-e-e-e-e-+
|               |
|      \0{      |
|               |
+-----+-+-------+
e \0* |0|   $   e
+-----+-+-------+

Ekspresi CoX^0oXsebenarnya diuraikan sebagai ((CoF)0)oX; yang oFdan oXadalah operator postfix dan gabungan dari token sarana Rangkaian horizontal. The ^memberikan penjajaran prioritas lebih tinggi kemudian oX, sehingga rotasi yang diterapkan pada seluruh sub-ekspresi. The oFmengoreksi orientasi Csetelah diputar oleh oX; jika tidak, bisa cocok dengan koordinat nol pertama dalam urutan pembacaan bahasa Inggris yang diputar.

e`C|:\0
e`       Match entire input against pattern:
    :    a grid whose cells match
  C      C
   |     or
     \0  literal 0.

Ini berarti bahwa semua karakter bukan nol harus terhubung dengan yang pertama. Grid specifier :secara teknis adalah operator postfix, tetapi C|:\0merupakan sintaksis untuk (C|\0):.

Zgarb
sumber
0

Perl 5 , 131 129 + 2 ( -ap) = 133 byte

push@a,[@F,0]}{push@a,[(0)x@F];$\=1;map{//;for$j(0..$#F){$b+=$a[$'][$j+$_]+$a[$'+$_][$j]for-1,1;$\*=$b||!$a[$'][$j];$b=0}}0..@a-2

Cobalah online!

Xcali
sumber
0

Python 2 , 211 163 150 byte

m,w=input()
def f(i):a=m[i];m[i]=0;[f(x)for x in(i+1,i-1,i+w,i-w)if(x>=0==(i/w-x/w)*(i%w-x%w))*a*m[x:]]
f(m.index((filter(abs,m)or[0])[0]))<any(m)<1>q

Cobalah online!

Output melalui kode keluar. Input adalah sebagai daftar 1d dan lebar matriks.

ovs
sumber