Überprüfen Sie, ob alle Nicht-Null-Elemente in einer Matrix verbunden sind

19

Eingang:

Eine Matrix mit ganzen Zahlen im Bereich [0 - 9] .

Herausforderung:

Bestimmen Sie, ob alle Nicht-Null-Elemente vertikal und / oder horizontal miteinander verbunden sind.

Ausgabe:

Ein wahrer Wert, wenn alle verbunden sind, und ein falscher Wert, wenn es Elemente / Gruppen ungleich Null gibt, die nicht mit anderen Elementen / Gruppen verbunden sind.

Testfälle:

Testfälle werden durch eine Linie getrennt. Testfälle können in bequemen Formaten findet hier ( großes Lob an Dada ).

Die folgenden sind alle miteinander verbunden und sollten einen wahrheitsgemäßen Wert zurückgeben:

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

Die folgenden sind alle nicht verbunden und sollten einen falschen Wert zurückgeben:

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

Das ist , also gewinnt die kürzeste Einsendung in jeder Sprache. Erklärungen sind erwünscht!


Inspiriert von dieser Herausforderung .

Stewie Griffin
quelle
Vielleicht sollte die Eingabe nur Einsen und Nullen (oder Wahrheiten und Falschen) enthalten, da es sich im Wesentlichen um verbundene Komponenten handelt.
NikoNyrh
Können wir Eingaben als ein 1d-Array und eine Anzahl von Spalten annehmen?
Ovs
@ovs sicher. Ich kann nicht sehen, dass es Ihnen Vorteile gegenüber anderen Leuten geben sollte, die bereits geantwortet haben.
Stewie Griffin
2
Verwandte : Wie viele Nullen müssen Sie ändern, um alle Nicht-Null-Elemente verbunden zu machen
dylnan
Verwandt : Zählen Sie die Anzahl der Komponenten (aber mit diagonalen Einträgen nebeneinander).
Mischa Lawrow

Antworten:

9

Retina 0.8.2 , 80 77 Bytes

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

Probieren Sie es online! Bearbeiten: 1 Byte dank @FryAmTheEggman gespeichert. Erläuterung:

T`d`@1

Vereinfachen Sie zu einem Array von @s und 1s.

1`1
_

Ändern Sie eine 1zu a _.

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

Fülle es von dem _bis zum angrenzenden 1s.

^\D+$

Prüfen Sie, ob noch 1s übrig sind.

Neil
quelle
@FryAmTheEggman Danke, und du hast mir eine Idee gegeben, wie ich noch zwei Bytes sparen kann!
Neil
7

JavaScript (ES6), 136 135 Bytes

Gibt einen Booleschen Wert zurück.

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

Testfälle

Kommentiert

Die rekursive Funktion g () sucht zunächst nach einer Nicht-Null-Zelle (solange das global definierte Flag z auf 0 gesetzt ist ) und beginnt von dort aus mit dem Füllen (sobald z! = 0 ist ).

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
quelle
7

MATL , 7 Bytes

4&1ZI2<

Dies ergibt eine Matrix, die alle Einsen als wahrheitsgemäße Ausgabe enthält, oder eine Matrix, die mindestens eine Null als falsch enthält . Probieren Sie es online!

Sie können auch die Richtigkeit / Falschheit überprüfen, indem Sie einen if- elseZweig in der Fußzeile hinzufügen . versuche es auch!

Oder überprüfen Sie alle Testfälle .

Erläuterung

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
quelle
1
Hinweis von OP: Im Zweifelsfall: Die Ausgaben sind einwandfrei und entsprechen dem verknüpften Metapost.
Stewie Griffin
Ich kann es kaum fassen, dass MATL / matlab ein Array von Zahlen als wahr ansieht, wenn es keine Nullen enthält. mathworks.com/help/matlab/ref/if.html (früherer Kommentar gelöscht)
Sparr
@Sparr (Eigentlich ist es genau dann , wenn es keine Nullen enthält und ist nicht leer .) Ich war auch verwirrt , als ich erfuhr , dass jede nicht leere Array truthy in anderen Sprachen ist
Luis Mendo
4

C 163 Bytes

Vielen Dank an @ user202729 für das Speichern von zwei Bytes!

*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;}

Durchläuft die Matrix, bis das erste Nicht-Null-Element gefunden wird. Hört dann für eine Weile auf zu schleifen und setzt rekursiv jedes Nicht-Null-Element, das mit dem gefundenen Element verbunden ist, auf Null. Durchläuft dann den Rest der Matrix und prüft, ob jedes Element jetzt Null ist.

Probieren Sie es online!

Abgerollt:

*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
quelle
2

Perl, 80 79 78 73 70 Bytes

Enthält +2für0a

Geben Sie die Eingabematrix ohne Leerzeichen in STDIN an (oder in der Tat als durch Leerzeichen getrennte Zeilen).

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

Einfacher zu lesen, wenn in einer Datei abgelegt:

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

Java 8, 226 Bytes

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){}}

Das hat eine ganze Weile gedauert und ich bin froh, dass es jetzt funktioniert.

Erläuterung:

Probieren Sie es online aus.

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
quelle
1

Jelly , 23 Bytes

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

Probieren Sie es online!


Erläuterung.

Das Programm kennzeichnet jede morphologische Komponente mit einer anderen Nummer und prüft dann, ob es weniger als 3 Nummern gibt. (einschließlich 0).

Betrachten Sie eine Zeile in der Matrix.

«Ḋ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]

Wenden Sie diese Funktion wiederholt für alle Zeilen und Spalten in der Matrix in allen Reihenfolgen an. Schließlich haben alle morphologischen Komponenten dieselbe Bezeichnung.

µ«Ḋ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.

Und schlussendlich...

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.
user202729
quelle
Imaginäre Kopfgeld, wenn Sie es in linearer Zeit tun können. Ich denke , es ist in Jelly nicht möglich ist, auch ¦nimmt O (n).
user202729
(natürlich ohne Python-
Auswertung
1

Haskell , 132 Bytes

 \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

extrahiert aus Löse Hitori Rätsel

indices mlistet die (line,cell)Positionen des Eingaberasters auf.

filter((/=0).(m!)) filtert alle Stellen mit Nicht-Null-Werten heraus.

splitAt 1 Partitioniert das erste Mitglied in eine Singleton-Liste neben einer Rest-Liste.

any(==1)[(b-d)^2+(p-q)^2|(d,q)<-f]sagt , wenn (b,p)die Grenze berührt f.

\(f,e)->partition(\(b,p)->touches(b,p)f)e spaltet Berührungen von noch nicht Berührungen ab.

until(null.fst)advanceFrontier wiederholt dies, bis die Grenze nicht mehr vorrücken kann.

null.snd prüft das Ergebnis, ob tatsächlich alle zu erreichenden Standorte erreicht wurden.

Probieren Sie es online!

Roman Czyborra
quelle
1

Schmutz , 37 Bytes

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

Druckt 1für Übereinstimmung und 0für keine Übereinstimmung. Probieren Sie es online!

Erläuterung

Das CNicht- Terminal stimmt mit jedem Nicht-Null-Zeichen überein, das mit dem ersten Nicht-Null-Zeichen der Matrix in der englischen Lesereihenfolge verbunden ist.

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.

Einige Erklärungen: eStimmt mit einem Rechteck mit der Breite oder Höhe Null überein, das Teil der Kante der Eingabematrix ist, und $ist ein "Platzhalter", der mit allem übereinstimmt. Der Ausdruck e/\0{/e\0*0$ekann wie folgt dargestellt werden:

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

Der Ausdruck CoX^0oXwird tatsächlich analysiert als ((CoF)0)oX; Die Operatoren oFund oXsind Postfix-Operatoren, und die Verkettung von Tokens bedeutet horizontale Verkettung. Die ^Nebeneinanderstellung hat dann eine höhere Priorität oX, sodass die Drehung auf den gesamten Unterausdruck angewendet wird. Das oFkorrigiert die Ausrichtung Cnach dem Drehen um oX; Andernfalls könnte es mit der ersten Koordinate ungleich Null in einer gedrehten Lesereihenfolge übereinstimmen.

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

Dies bedeutet, dass alle Zeichen ungleich Null mit dem ersten Zeichen verbunden sein müssen. Der Grid-Spezifizierer :ist technisch gesehen ein Postfix-Operator, C|:\0ist jedoch syntaktischer Zucker für (C|\0):.

Zgarb
quelle
0

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

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

Probieren Sie es online!

Xcali
quelle
0

Python 2 , 211 163 150 Bytes

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

Probieren Sie es online!

Die Ausgabe erfolgt über den Exit-Code. Die Eingabe erfolgt als 1d-Liste und die Breite der Matrix.

ovs
quelle