# Check if all non-zero elements in a matrix are connected

### Input:

A matrix containing integers in the range [0 - 9].

### Challenge:

Determine if all non-zero elements are connected to each other vertically and/or horizontally.

### Output:

A truthy value if all are connected, and a falsy value if there are non-zero elements/groups that aren't connected to other elements/groups.

### Test cases:

Test cases are separated by line. Test cases can be found in more convenient formats here (Kudos to Dada).

The following are all connected and should return a truthy value:

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


The following are all not-connected, and should return a falsy value:

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


This is , so the shortest submission in each language wins. Explanations are encouraged!

Inspired by this challenge.

• Perhaps the input should contain only ones and zeros (or truthys and falsys), as this is essentially about connected components. – NikoNyrh Jan 30 '18 at 14:15
• Can we take input as an 1d array and a number of columns? – ovs Jan 30 '18 at 15:05
• @ovs sure. I can't see that it should give you any advantages over other people that have already answered. – Stewie Griffin Jan 30 '18 at 17:06
• Related: how many zeroes do you need to change to make all nonzero elements connected – dylnan Jan 30 '18 at 17:34
• Related: count the number of components (but with diagonal entries adjacent). – Misha Lavrov Feb 5 '18 at 14:53

# Retina 0.8.2, 80 77 bytes

Td@1
11
_
+m^((.)*)(1|_)( |.*¶(?<-2>.)*(?(2)(?!)))(?!\3)[1_]
$1_$4_
^\D+$ Try it online! Edit: Saved 1 byte thanks to @FryAmTheEggman. Explanation: Td@1  Simplify to an array of @s and 1s. 11 _  Change one 1 to a _. +m^((.)*)(1|_)( |.*¶(?<-2>.)*(?(2)(?!)))(?!\3)[1_]$1_$4_  Flood fill from the _ to adjacent 1s. ^\D+$


Test whether there are any 1s left.

• @FryAmTheEggman Thanks, and you gave me an idea as to how to save another two bytes too! – Neil Jan 31 '18 at 9:33

# JavaScript (ES6), 136 135 bytes

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


### Test cases

let f =

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

console.log('[Truthy]')

console.log(f([

]))
console.log(f([
[0,0]
]))
console.log(f([
[1,1,1],
[0,0,0]
]))
console.log(f([
[1,0,0],
[1,1,1],
[0,0,1]
]))
console.log(f([
[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]
]))

console.log('[Falsy]')

console.log(f([
[0,1],
[1,0]
]))
console.log(f([
[1,1,1,0],
[0,0,0,2],
[0,0,0,5]
]))
console.log(f([
[0,0,5,2],
[1,2,0,0],
[5,3,2,1],
[5,7,3,2]
]))
console.log(f([
[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]
]))

### Commented

The recursive function g() first looks for a non-zero cell (as long as the globally-defined flag z is set to 0) and then starts flood-filling from there (as soon as 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()


# MATL, 7 bytes

4&1ZI2<


This gives a matrix containing all ones as truthy output, or a matrix containing at least a zero as falsy. Try it online!

You can also verify truthiness/falsiness adding an if-else branch at the footer; try it too!

### Explanation

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

• OP's note: in case there's any doubt: the outputs are perfectly fine and adheres to the linked meta post. – Stewie Griffin Jan 30 '18 at 21:59
• It's blowing my mind that MATL/matlab considers an array of numbers to be truthy IFF it contains no zeros. mathworks.com/help/matlab/ref/if.html (earlier comment deleted) – Sparr Jan 31 '18 at 1:56
• @Sparr (Actually, it is iff it contains no zeros and is not empty.) I was also confused when I learned that any nonempty array is truthy in other languages – Luis Mendo Jan 31 '18 at 10:13

# Wolfram Language (Mathematica), 54 bytes

Saved 2 bytes thanks to user202729.

Max@MorphologicalComponents[#,CornerNeighbors->1<0]<2&


Try it online!

# C, 163 bytes

Thanks to @user202729 for saving two 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;}


Loops through the matrix until it finds the first non-zero element. Then stops looping for a while and recursively sets every non-zero element connected to the found element to zero. Then loops through the rest of the matrix checking if every element is now zero.

Try it online!

Unrolled:

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


# Perl, 80797873 70 bytes

Includes +2 for 0a

Give the input matrix without spaces on STDIN (or in fact as rows separated by any kind of whitespace)

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  Easier to read if put in a 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!/}/


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


This took quite a while, so I'm glad it's working now..

Explanation:

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


# APL (Dyalog Unicode), 36 bytesSBCS

{2≥≢∪0,,(⍉××3⌈/0,,∘0)⍣2⍣≡⍵}××⍴⍴⍳∘≢∘,


Try it online!

# Jelly, 23 bytes

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


Try it online!

## Explanation.

The program labels each morphological components with a different numbers, then check if there are less than 3 numbers. (including 0).

Consider a row in the 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]


Repeatedly apply this function for all row and columns in the matrix, in all orders, eventually all morphological components will have the same label.

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


And finally...

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.

• Imaginary bounty if you can do it in linear time. I think it's not possible in Jelly, even ¦ takes O(n). – user202729 Jan 31 '18 at 7:20
• (without Python eval, of course) – user202729 Jan 31 '18 at 7:32

 \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  extracted from Solve Hitori Puzzles indices m lists the (line,cell) locations of the input grid. filter((/=0).(m!)) filters out all locations with non-zero values. splitAt 1 partitions off the first member into a singleton list next to a rest list. any(==1)[(b-d)^2+(p-q)^2|(d,q)<-f] tells if (b,p) touches the frontier f. \(f,e)->partition(\(b,p)->touches(b,p)f)e splits off touchers from not[yet]touchers. until(null.fst)advanceFrontier repeats this until the frontier can advance no further. null.snd looks at the result whether all locations to be reached were indeed reached. Try it online! # Grime, 37 bytes C=[,0]&<e/\0{/e\0*0$e|CoF^0oX
eC|:\0


Prints 1 for match and 0 for no match. Try it online!

## Explanation

The nonterminal C matches any nonzero character that is connected to the first nonzero character of the matrix in the English reading order.

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.  Some explanation: e matches a rectangle of zero width or height that's part of the edge of the input matrix, and $ is a "wildcard" that matches anything. The expression e/\0{/e\0*0$e can be visualized as follows: +-e-e-e-e-e-e-e-+ | | | \0{ | | | +-----+-+-------+ e \0* |0|$   e
+-----+-+-------+


The expression CoX^0oX is actually parsed as ((CoF)0)oX; the oF and oX are postfix operators and concatenation of tokens means horizontal concatenation. The ^ gives juxtaposition a higher precedence then oX, so the rotation is applied to the entire sub-expression. The oF corrects the orientation of C after it is rotated by oX; otherwise it could match the first nonzero coordinate in a rotated English reading order.

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


This means that all nonzero characters must be connected to the first one. The grid specifier : is technically a postfix operator, but C|:\0 is syntactic sugar for (C|\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


Try it online!

# Python 2, 211163 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)))<any(m)<1>q
`

Try it online!

Output is via exit code. Input is as an 1d list and the width of the matrix.