Entrada:

Una matriz que contiene enteros en el rango [0 - 9] .

Desafío:

Determine si todos los elementos distintos de cero están conectados entre sí verticalmente y / u horizontalmente.

Salida:

Un valor verdadero si todos están conectados, y un valor falso si hay elementos / grupos distintos de cero que no están conectados a otros elementos / grupos.

Casos de prueba:

Los casos de prueba están separados por línea. Los casos de prueba se pueden encontrar en formatos más convenientes aquí ( Felicitaciones a Dada ).

Los siguientes están todos conectados y deberían devolver un valor verdadero:

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

Los siguientes no están todos conectados y deberían devolver un valor falso:

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

Este es el código de golf , por lo que gana la presentación más corta en cada idioma. ¡Se alientan las explicaciones!

Inspirado en este desafío .

Retina 0.8.2 , 80 77 bytes

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

Pruébalo en línea! Editar: guardado 1 byte gracias a @FryAmTheEggman. Explicación:

T`d`@1

Simplifique a una matriz de @sy 1s.

1`1
_

Cambiar uno 1a a _.

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

Relleno de inundación desde el s _adyacente 1.

^\D+$

Comprueba si quedan algunos 1s.

JavaScript (ES6), 136 135 bytes

Devuelve un booleano.

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

Casos de prueba

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([
  [0]
]))
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]
]))

Comentado

La función recursiva g () primero busca una celda que no sea cero (siempre que el indicador globalmente definido z esté establecido en 0 ) y luego comienza el llenado de inundación desde allí (tan pronto como 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<

Esto proporciona una matriz que contiene todos los resultados verdaderos , o una matriz que contiene al menos un cero como falso .Pruébalo en línea!

También puede verificar la veracidad / falsedad agregando una if- elserama en el pie de página; ¡pruébalo también!

O verificar todos los casos de prueba .

Explicación

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

Wolfram Language (Mathematica) , 54 bytes

Guardado 2 bytes gracias al usuario202729.

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

Pruébalo en línea!

C, 163 bytes

¡Gracias a @ user202729 por guardar dos 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;}

Recorre la matriz en bucle hasta que encuentra el primer elemento distinto de cero. Luego deja de recorrer un momento y establece recursivamente todos los elementos que no son cero conectados al elemento encontrado a cero. Luego recorre el resto de la matriz para verificar si cada elemento es ahora cero.

Pruébalo en línea!

Desenrollado:

*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, 80 79 78 73 70 bytes

Incluye +2para0a

Dé la matriz de entrada sin espacios en STDIN (o de hecho como filas separadas por cualquier tipo de espacio en blanco)

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

Más fácil de leer si se coloca en un archivo:

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

Esto tomó bastante tiempo, así que me alegra que esté funcionando ahora ...

Explicación:

Pruébalo en línea.

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) , ^{SBCS de} 36 bytes

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

Pruébalo en línea!

Jalea , 23 bytes

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

Pruébalo en línea!

Explicación.

El programa etiqueta cada componente morfológico con un número diferente, luego verifica si hay menos de 3 números. (incluido 0)

Considere una fila en la matriz.

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

Aplica repetidamente esta función para todas las filas y columnas de la matriz, en todos los órdenes, eventualmente todos los componentes morfológicos tendrán la misma etiqueta.

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

Y finalmente...

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.

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

extraído de Solve Hitori Puzzles

indices menumera las (line,cell)ubicaciones de la cuadrícula de entrada.

filter((/=0).(m!)) filtra todas las ubicaciones con valores distintos de cero.

splitAt 1 divide el primer miembro en una lista singleton junto a una lista de descanso.

any(==1)[(b-d)^2+(p-q)^2|(d,q)<-f]le dice si (b,p)toca la frontera f.

\(f,e)->partition(\(b,p)->touches(b,p)f)e se separa de los tocadores de los que no [todavía] tocan.

until(null.fst)advanceFrontier repite esto hasta que la frontera no pueda avanzar más.

null.snd mira el resultado si se alcanzaron todas las ubicaciones a las que se debe llegar.

Pruébalo en línea!

Grime , 37 bytes

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

Imprime 1por partido y 0sin partido. Pruébalo en línea!

Explicación

El no terminal Ccoincide con cualquier carácter distinto de cero que esté conectado al primer carácter distinto de cero de la matriz en el orden de lectura en inglés.

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.

Alguna explicación: ecoincide con un rectángulo de ancho o alto cero que es parte del borde de la matriz de entrada, y $es un "comodín" que coincide con cualquier cosa. La expresión e/\0{/e\0*0$ese puede visualizar de la siguiente manera:

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

La expresión en CoX^0oXrealidad se analiza como ((CoF)0)oX; el oFy oXson operadores de sufijo y concatenación de medios fichas concatenación horizontal. los^ da yuxtaposición una prioridad más alta entonces oX, por lo que la rotación se aplica a la totalidad de sub-expresión. El oFcorrige la orientación de Cdespués de que se gira oX; de lo contrario, podría coincidir con la primera coordenada distinta de cero en un orden de lectura en inglés rotado.

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

Esto significa que todos los caracteres distintos de cero deben estar conectados al primero. El especificador de cuadrícula :es técnicamente un operador postfix, peroC|:\0 es azúcar sintáctico para (C|\0):.

Perl 5 , 131129 + 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

Pruébalo en línea!

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

Pruébalo en línea!

La salida es a través del código de salida. La entrada es como una lista 1d y el ancho de la matriz.