Pour trouver des îles de 1 et 0 dans la matrice

29

Étant donné une matrice bidimensionnelle de 0 et 1s. Trouvez le nombre d'îles pour 1 et 0 où les voisins sont uniquement à l'horizontale et à la verticale.

Given input:

1 1 1 0
1 1 1 0

output = 1 1
Number of 1s island = 1

xxx-
xxx-

Number of 0s island = 1 

---x
---x

------------------------------

Given input:

0 0 0 0
1 1 1 1
0 0 0 0
1 1 1 1

output = 2 2
Number of 1s island = 2

----
xxxx  <-- an island of 1s
----
xxxx  <-- another island of 1s

Number of 0s island = 2

xxxx  <-- an island
----
xxxx  <-- another island
----

------------------------------

Given input:

1 0 0
0 0 0
0 0 1
output = 2 1
Number for 1's island = 2:

x--  <-- an island of 1s
---
--x  <-- an island of 1s

Number of 0's island = 1:

-xx  \
xxx   > 1 big island of 0s
xx-  / 


------------------------------

Given input:

1 1 0
1 0 0
output = 1 1
Number for 1's island =1 and number of 0's island = 1

------------------------------

Given input:

1 1
1 1
output = 1 0
Number for 1's island =1 and number of 0's island = 0
KB joy
la source
11
Vous devez ajouter un testcase [[1,0];[0,1]]pour vous assurer que la connectivité diagonale n'est pas incluse
Sanchises
8
Je suggérerais que la sortie puisse être dans l'un ou l'autre ordre tant que l'ordre est spécifié - cela n'ajoute aucune valeur pour forcer une commande
streetster
8
Bienvenue sur le site!
Arnauld
1
Ce qui a été répondu dans les commentaires doit être clarifié dans le corps du défi. Et plus précisément, si vous voulez vraiment que nous renvoyions 1 avant 0, cela doit être clairement indiqué.
Arnauld
4
Cas de test suggéré: 11111 / 10001 / 10101 / 10001 / 111112 1
Kevin Cruijssen

Réponses:

16

APL (Dyalog Unicode) , 29 28 octets SBCS

-1 grâce à @ Adám

{≢∪∨.∧⍨⍣≡2>+/↑|∘.-⍨⍸⍵}¨⊂,~∘⊂

Essayez-le en ligne!

⊂,~∘⊂ la matrice et sa négation

{ pour chacun d'eux

⍸⍵ liste des paires de cordes de 1s

+/↑|∘.-⍨ matrice des distances de manhattan

2> matrice voisine

∨.∧⍨⍣≡ fermeture transitive

≢∪ nombre de lignes uniques

ngn
la source
c'est vraiment intelligent. pourriez-vous expliquer pourquoi la ligne finale est garantie de fonctionner - c'est-à-dire pourquoi les lignes uniques sont équivalentes à la réponse. aussi, la "fermeture transitive" est-elle comme celle de J ^:_?
Jonah
1
@Jonah voir le chat
ngn
16

J , 57 octets

,&([:(0#@-.~~.@,)](*@[*[:>./((,-)#:i.3)|.!.0])^:_ i.@$)-.

Essayez-le en ligne!

C'est l'une de celles où l'idée est incroyablement simple (et je pense que c'est amusant), mais son exécution avait une certaine longueur mécanique qui masque la simplicité ... par exemple, déplacer la matrice d'origine dans toutes les directions avec un remplissage à 0 est le verbeux ((,-)#:i.3) |.!.0.

Il est probable que cette longévité mécanique puisse être étudiée plus loin, et je peux essayer demain soir, mais j'en posterai le point crucial maintenant.

Disons que notre contribution est:

0 0 0 0
1 1 1 1
0 0 0 0
1 1 1 1

Nous commençons avec une matrice d'entiers uniques de la même taille:

 0  1  2  3
 4  5  6  7
 8  9 10 11
12 13 14 15

Ensuite, pour chaque cellule, nous trouvons le maximum de tous ses voisins, et multiplions par le masque de saisie:

 0  0  0  0
 8  9 10 11
 0  0  0  0
13 14 15 15

Nous répétons ce processus jusqu'à ce que la matrice cesse de changer:

 0  0  0  0
11 11 11 11
 0  0  0  0
15 15 15 15

Et puis comptez le nombre d'éléments uniques non différents de zéro. Cela nous indique le nombre d'îlots.

Nous appliquons le même processus à "1 moins l'entrée" pour obtenir le nombre d'îlots 0.

Jonas
la source
3
Cela ressemble beaucoup à un mécanisme de "remplissage par inondation", vraiment soigné.
Matthieu M.
7

JavaScript (ES7),  138 ... 107106  octets

Renvoie un tableau [ones, zeros].

f=(m,X,Y,V=.5,c=[0,0])=>m.map((r,y)=>r.map((v,x)=>V-v|(x-X)**2+(y-Y)**2>1||f(m,x,y,v,r[c[v^1]++,x]=2)))&&c

Essayez-le en ligne!

Comment?

01c[0]c[1]2

Pour économiser des octets, le même code exact est utilisé à la fois pour l'itération racine et les itérations récursives, mais il se comporte un peu différemment.

Lors de la première itération:

  • V=0.5Vv0v=0v=1
  • XY(xX)2+(yY)2(x,y)

Lors des itérations récursives:

  • c2c[v ^ 1]++c

Commenté

f = (                 // f is a recursive function taking:
  m,                  //   m[]  = input binary matrix
  X, Y,               //   X, Y = coordinates of the previous cell, initially undefined
  V = .5,             //   V    = value of the previous cell, initially set to 0.5
                      //          so that the integer part of V - v is 0 for v = 0 or 1
  c = [0, 0]          //   c[]  = array of counters of 1's and 0's islands
) =>                  //          (or an integer when called recursively)
  m.map((r, y) =>     // for each row r[] at position y in m[]:
    r.map((v, x) =>   //   for each value v at position x in r[]:
      V - v |         //     abort if |V - v| ≥ 1
      (x - X) ** 2 +  //     or X and Y are defined and the quadrance between
      (y - Y) ** 2    //     (X, Y) and (x, y)
      > 1 ||          //     is greater than 1
      f(              //     otherwise, do a recursive call to f:
        m,            //       leave m[] unchanged
        x, y,         //       pass the new coordinates
        v,            //       pass the new reference value
        r[c[v ^ 1]++, //       increment c[v ^ 1] (ineffective if c is an integer)
          x           //       and set the current cell ...
        ] = 2         //       ... to 2
      )               //     end of recursive call
    )                 //   end of inner map()
  ) && c              // end of outer map(); return c
Arnauld
la source
Ce code ne fonctionne pas pour les grandes matrices comme 100 * 100, avec seulement 1 ou 0 en raison d'un débordement de pile.
KB joy
3
@KBjoy Sauf indication contraire explicite dans le défi, notre règle par défaut est que nous ne nous soucions pas des limites d'implémentation tant que l'algorithme sous-jacent fonctionne en théorie pour n'importe quelle entrée. ( Voici un méta post à ce sujet, mais il y en a probablement un plus pertinent quelque part.)
Arnauld
7

MATL , 14 12 octets

,G@-K&1ZIugs

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

,        % Do twice
  G      %   Push input
  @      %   Push iteration index: first 0, then 1
  -      %   Subtract. This converts 0 and 1 into -1 and 0 in the second iteration 
  K      %   Push 4
  &1ZI   %   Label connected components of matrix using 4-connectedness. Zeros in the
         %   matrix are background. This replaces the nonzeros by 1, 2, 3, ..., where 
         %   each number defines a connected component
  u      %   Unique values. This gives [0; 1; 2; ..., L], where L is the number of
         %   connected components.
  g      %   Convert nonzeros to 1
  s      %   Sum. This gives L, to be output
         % End (implicit).
         % Display stack (implicit)
Luis Mendo
la source
6

K (ngn / k) , 60 55 51 50 46 octets

{#?{|/'x*\:x}/2>+/x*x:x-\:'x:(0,#*x)\&,/x}'~:\

Essayez-le en ligne!

~:\ une paire de l'entrée et sa négation (littéralement: nier itérer-converger)

{ }' pour chaque

,/x aplatir l'argument

&où sont les 1? - liste des indices

(0,#*x)\ largeur divmod (entrée) pour obtenir deux listes distinctes pour ys et xs

x-\:'x: distances par axe ∆x et ∆y

x*x: les mettre au carré

+/ ajouter ∆x² et ∆y²

2> matrice voisine

{|/'x*\:x}/ fermeture transitive

#? compter les lignes uniques

ngn
la source
Après avoir vu votre réponse, je suis heureux de ne pas avoir essayé de répondre à celle-ci en K :)
streetster
2
@streetster haha, merci! ce n'est pas l'effet que je voulais :) j'aimerais en fait encourager les gens à apprendre (n'importe quel dialecte) le k et le golf
ngn
6

Wolfram Language (Mathematica) , 64 62 octets

Max@MorphologicalComponents[#,CornerNeighbors->1<0]&/@{#,1-#}&

Essayez-le en ligne!

Merci à attinat : on peut écrire 1<0au lieu de Falseet économiser deux octets.

version sans golf:

F[M_] := {Max[MorphologicalComponents[M,   CornerNeighbors -> False]], 
          Max[MorphologicalComponents[1-M, CornerNeighbors -> False]]}

Il y a, bien sûr, un module intégré MathematicaMorphologicalComponents qui prend un tableau (ou une image) et le renvoie avec les pixels de chaque îlot morphologiquement connecté remplacés par l'index de l'îlot. La prise Maxde ce résultat donne le nombre d'îles (les zéros d'arrière-plan sont laissés à zéro et l'indice d'îlot commence à 1). Nous devons le faire séparément pour le tableau (en donnant le nombre d'îlots) et un moins le tableau (en donnant le nombre d'îlots 0). Pour s'assurer que les voisins en diagonale ne comptent pas comme voisins, l'option CornerNeighbors->Falsedoit être donnée.

romain
la source
-2 octets car les inégalités ont une priorité plus élevée queRule
attinat
5

Python 3, 144 127 octets

Cette solution utilise cv2la puissance de traitement d'image impressionnante. Malgré les noms de méthode moins impressionnants, super longs et lisibles de cv, il bat les deux autres réponses Python!

Golfé:

import cv2,numpy as n
f=lambda b:n.amax(cv2.connectedComponents(b*255,0,4)[1])
def g(a):b=n.array(a,n.uint8);print(f(1-b),f(b))

Étendu:

import cv2
import numpy as np

# Finds the number of connected 1 regions 
def get_components(binary_map):
    _, labels = cv2.connectedComponents(binary_map*255, connectivity=4) # default connectivity is 8
    # labels is a 2d array of the binary map but with 0, 1, 2, etc. marking the connected regions
    components = np.amax(labels)
    return components

# Takes a 2d array of 0s and 1s and returns the number of connected regions
def solve(array): 
    binary_map = np.array(input_map, dtype=np.uint8)
    black_regions = get_components(1 - binary_map) # 0s
    white_regions = get_components(binary_map) # 1s
    return (black_regions, white_regions)
Daniel
la source
Je ne connais pas trop Python, mais pourquoi avez-vous besoin des noms d'arguments explicites? N'est-ce pas juste 4au lieu de connectivity=4et n.uint8au lieu de dtype=n.uint8possible?
Kevin Cruijssen
@KevinCruijssen, vous avez besoin des noms d'argument si vous ignorez les arguments facultatifs. En jetant un œil aux documents, je n'ai en fait pas à sauter, ce qui me fait économiser beaucoup d'octets. Merci!
Daniel
Ah ok, je pensais que c'était quelque chose comme ça, mais quand je viens de regarder les documents, je ne pouvais trouver qu'une seule cv2.connectedComponentsméthode, donc j'étais confus et pensais qu'il pourrait y avoir une raison différente pour avoir besoin des noms d'argument. Comme je l'ai dit, je ne connais pas trop Python. Tout ce que j'en ai appris, c'est d'ici sur le CCGC. ;) Mais il est logique d'utiliser les noms de variables pour ignorer les autres arguments facultatifs.
Kevin Cruijssen
1
Très agréable! J'ai trouvé un compilateur en ligne qui inclut le module cv2 ici .
Jitse
5

J , 46 44 43 octets

-1 octet grâce à @miles

,&#&~.&([:+./ .*~^:_:2>1#.[:|@-"1/~4$.$.)-.

Essayez-le en ligne!

tests et l' ,& -.emballage volés à la réponse de @ jonah

,& -. pour l'entrée et sa négation:

4$.$. (y, x) coordonnées des 1 comme une matrice n × 2

1#.[:|@-"1/~ distances manhattan: abs (∆x) + abs (∆y)

2> matrice voisine

[:+./ .*~^:_: fermeture transitive

#&~.&( ) nombre de lignes uniques

ngn
la source
1
vous pouvez composer la longueur et l'unique pour enregistrer un autre octet, c'est- ,&#&~.à- dire pour éviter le plafond[:
miles
@miles merci
ngn
3

Retina 0.8.2 , 155 octets

s`1(.*)
;$1a
}+`(?<=(.)*)(1|;)(.*¶(?<-1>.)*(?(1)$))?(?!\2)[1;]
;$3;
s`0(.*)
:$1b
}+`(?<=(.)*)(0|:)(.*¶(?<-1>.)*(?(1)$))?(?!\2)[0:]
:$3:
\W+(a*)(b*)
$.1 $.2

Essayez-le en ligne! Le lien inclut un cas de test. Explication:

s`1(.*)
;$1a

S'il y a un 1, changez-le en ;et ajoutez-en un aà la fin de l'entrée afin qu'il ne soit pas sur le chemin.

}+`(?<=(.)*)(1|;)(.*¶(?<-1>.)*(?(1)$))?(?!\2)[1;]
;$3;

Inondez remplissez tout 1s adjacent avec ;s.

}

Répétez jusqu'à ce que toutes les îles de 1s aient été transformées en ;s.

s`0(.*)
:$1b

S'il y a un 0, changez-le en :et ajoutez un bà la fin de l'entrée afin qu'il ne soit pas sur le chemin.

+`(?<=(.)*)(0|:)(.*¶(?<-1>.)*(?(1)$))?(?!\2)[0:]
:$3:

Inondez remplissez tout 0s adjacent avec :s.

}

Répétez jusqu'à ce que toutes les îles de 0s aient été transformées en :s.

\W+(a*)(b*)
$.1 $.2

Comptez séparément le nombre d'îles de 1s et 0s.

Neil
la source
3

Haskell , 228 227 225 224 octets

import Data.List
z=zipWith
a!b=div(max(a*a)(a*b))a
l x=z(!)(z(!)x(0:x))$tail x++[0]
s=(\x->length.($x).filter<$>[(>0),(<0)]).nub.(>>=id).(until=<<((==)=<<))((.)>>=id$transpose.map l).z(\i->z(\j x->2^i*j*(2*x-1))[1,3..])[1..]

Essayez-le en ligne!

Explication:

L'idée de cette solution est la suivante: initialiser la matrice avec des valeurs uniques dans chaque cellule, positives pour 1et négatives pour 0. Ensuite, comparez à plusieurs reprises chaque cellule avec ses voisins et, si le voisin a le même signe mais un nombre avec une valeur absolue plus grande, remplacez le numéro de la cellule par le numéro du voisin. Une fois que cela atteint un point fixe, comptez le nombre de nombres positifs distincts pour le nombre de 1régions et les nombres négatifs distincts pour le nombre de 0régions.

Dans du code:

s=(\x->length.($x).filter<$>[(>0),(<0)]).nub.(>>=id).(until=<<((==)=<<))((.)>>=id$transpose.map l).z(\i->z(\j x->2^i*j*(2*x-1))[1,3..])[1..]

peut être séparé en prétraitement (attribution de numéros aux cellules), itération et post-traitement (comptage des cellules)

Prétraitement

La partie prétraitement est la fonction

z(\i->z(\j x->2^i*j*(2*x-1))[1,3..])[1..]

Qui utilise zcomme abréviation pour zipWithraser quelques octets. Ce que nous faisons ici est de compresser le tableau bidimensionnel avec des indices entiers sur les lignes et des indices entiers impairs sur les colonnes. Nous faisons cela car nous pouvons construire un entier unique à partir d'une paire d'entiers en (i,j)utilisant la formule (2^i)*(2j+1). Si nous ne générons que des entiers impairs pour j, nous pouvons ignorer le calcul de 2*j+1, en économisant trois octets.

Avec le nombre unique, il ne nous reste plus qu'à multiplier dans un signe basé sur la valeur dans la matrice, qui est obtenue comme 2*x-1

Itération

L'itération se fait par

(until=<<((==)=<<))((.)>>=id$transpose.map l)

Étant donné que l'entrée se présente sous la forme d'une liste de listes, nous effectuons la comparaison des voisins sur chaque ligne, transposons la matrice, effectuons à nouveau la comparaison sur chaque ligne (qui, en raison de la transposition, est ce qu'étaient les colonnes auparavant) et transposons à nouveau. Le code qui accomplit l'une de ces étapes est

((.)>>=id$transpose.map l)

où se ltrouve la fonction de comparaison (détaillée ci-dessous) et transpose.map leffectue la moitié des étapes de comparaison et de transposition. (.)>>=idexécute son argument deux fois, étant la forme sans point \f -> f.fet d'un octet plus court dans ce cas en raison des règles de priorité de l'opérateur.

lest défini dans la ligne ci-dessus comme l x=z(!)(z(!)x(0:x))$tail x++[0]. Ce code effectue un opérateur de comparaison (!)(voir ci-dessous) sur chaque cellule avec d'abord son voisin gauche, puis avec son voisin droit, en zippant la liste xavec la liste décalée à droite 0:xet la liste décalée à gauche tail x++[0]tour à tour. Nous utilisons des zéros pour garnir les listes décalées, car elles ne peuvent jamais se produire dans la matrice prétraitée.

a!best défini dans la ligne au-dessus de cela comme a!b=div(max(a*a)(a*b))a. Ce que nous voulons faire ici, c'est la distinction de cas suivante:

  • Si sgn(a) = -sgn(b), nous avons deux zones opposées dans la matrice et ne souhaitons pas les unifier, areste inchangé
  • Si sgn(b) = 0, nous avons le cas du coin où best le rembourrage et areste donc inchangé
  • Si sgn(a) = sgn(b), nous souhaitons unifier les deux zones et prendre celle avec la plus grande valeur absolue (pour des raisons de commodité).

Notez que sgn(a)cela ne peut jamais l'être 0. Nous accomplissons cela avec la formule donnée. Si les signes de aet bdiffèrent, a*best inférieur ou égal à zéro, tandis que a*aest toujours supérieur à zéro, nous le sélectionnons donc comme le maximum et divisons avec apour revenir a. Sinon, max(a*a)(a*b)est abs(a)*max(abs(a),(abs(b)), et en divisant cela par a, nous obtenons sgn(a)*max(abs(a),abs(b)), qui est le nombre avec la plus grande valeur absolue.

Pour itérer la fonction ((.)>>=id$transpose.map l)jusqu'à ce qu'elle atteigne un point fixe, nous utilisons (until=<<((==)=<<)), qui est tiré de cette réponse stackoverflow .

Post-traitement

Pour le post-traitement, nous utilisons la partie

(\x->length.($x).filter<$>[(>0),(<0)]).nub.(>>=id)

qui est juste une collection d'étapes.

(>>=id)écrase la liste des listes en une seule liste, nubsupprime les doubles, (\x->length.($x).filter<$>[(>0),(<0)])partitionne la liste en une paire de listes, une pour les nombres positifs et l'autre pour les nombres négatifs, et calcule leurs longueurs.

Sacchan
la source
2

Java 10, 359 355 281 280 261 246 octets

int[][]M;m->{int c[]={0,0},i=m.length,j,t;for(M=m;i-->0;)for(j=m[i].length;j-->0;)if((t=M[i][j])<2)c[t^1]+=f(t,i,j);return c;}int f(int v,int x,int y){try{if(M[x][y]==v){M[x][y]|=2;f(v,x+1,y);f(v,x,y+1);f(v,x-1,y);f(v,x,y-1);}}finally{return 1;}}

-74 octets grâce à @NahuelFouilleul .

Essayez-le en ligne.

Explication:

int[][]M;              // Integer-matrix on class-level, uninitialized

m->{                   // Method with integer-matrix parameter and integer-array return-type
  int c[]={0,0}        //  Counters for the islands of 1s/0s, starting both at 0
      i=m.length,      //  Index of the rows
      j,               //  Index of the columns
      t;               //  Temp-value to decrease the byte-count
  for(M=m;             //  Set the class-level matrix to the input-matrix
      i-->0;)          //  Loop over the rows
    for(j=m[i].length;j-->0)
                       //   Inner loop over the columns
      if((t=M[i][j])   //    Set the temp value `t` to the value of the current cell
         <2)           //    And if this value is a 0 or 1:
        c[t^1]+=       //     Increase the corresponding counter by:
          f(t,i,j);    //      Call the recursive flood-fill method with value `t`
                       //      Which always returns 1 to increase the counter
  return c;}           //  After the nested loops: return the counters-array as result

// Recursive method with value and cell-coordinate as parameters,
// This method will flood-fill the matrix, where 0 becomes 2 and 1 becomes 3
int f(int v,int x,int y){
  try{if(M[x][y]==v){  //   If the cell contains the given value:
    M[x][y]|=2;        //    Fill the cell with 0→2 or 1→3 depending on the value
    f(v,x+1,y);        //    Do a recursive call downwards
    f(v,x,y+1);        //    Do a recursive call towards the right
    f(v,x-1,y);        //    Do a recursive call upwards
    f(v,x,y-1);}       //    Do a recursive call towards the left
  }finally{return 1;}} //  Ignore any ArrayIndexOutOfBoundsExceptions with a finally-return,
                       //  which is shorter than manual checks
                       //  And return 1 to increase the counter
Kevin Cruijssen
la source
1
-74 octets , supprimant le clone et utilisant |=2: 0 -> 2 et 1 -> 3, mais a >0été changé en==1
Nahuel Fouilleul
désolé d'avoir dû supprimer les tests pour que le lien tio tienne dans les commentaires
Nahuel Fouilleul
@NahuelFouilleul Merci, utilisation intelligente |=2! Et je pourrais toujours utiliser à la <2place de ==1-1 octet en vérifiant d'abord 0(et donc ils sont changés en 2, puis en utilisant le <2pour vérifier 1(qui sont changés en 3).)
Kevin Cruijssen
2

Python 3 , 167 octets

def f(m):
 n=[0,0];i=-2
 for r in m:
  j=0;i+=1
  for c in r:n[c^1]+=1-((i>=0)*(m[i][j]==c)*(1+({*r[:j]}=={c})*({*m[i][:j]}=={c^1}))or(j>0)*(r[j-1]==c));j+=1
 print(n)

Essayez-le en ligne!


Python 2 , 168 octets

def f(m):
 n=[0,0];i=-2
 for r in m:
	j=0;i+=1
	for c in r:n[c^1]+=1-((i>=0)*(m[i][j]==c)*(1+(set(r[:j])=={c})*(set(m[i][:j])=={c^1}))or(j>0)*(r[j-1]==c));j+=1
 print n

Essayez-le en ligne!

-2 octets grâce à Kevin Cruijssen

Correction de formatage +2 octets

Explication

Un compteur est conservé pendant 0s et 1s. Pour chaque entrée de la matrice, les actions suivantes sont effectuées:

  • Augmenter le compteur de la valeur actuelle de 1
  • Si la même valeur existe directement au-dessus ou à gauche, diminuez de 1

Il en résulte un faux positif pour les cas alignés à gauche comme

0 0 1
1 1 1

ou

0 1
1 1

Si une telle situation se présente, le compteur est diminué de 1.

La valeur de retour est [#1, #0]

Jitse
la source
1
J'ai bien peur que le PO mentionné dans le deuxième commentaire de l'ordre soit [#1, #0]. Bit imo inutile pour appliquer cela, mais c'est ce qu'il est pour l'instant. Quoi qu'il en soit, vous pouvez jouer au golf l' {not c}à {c^1}, et résoudre le problème je l' ai mentionné en changeant n[c]+=à n[c^1]+=une question similaire. Belle réponse cependant, +1 de ma part. :)
Kevin Cruijssen
Ah, tu as raison. Merci!
Jitse
1

Perl 5 ( -0777p), 110 octets

Peut être amélioré, utilise une expression régulière pour remplacer 1par 3, puis 0par 2.

/
/;$m="(.{@-})?";sub f{($a,$b,$c)=@_;1while s/$b$m\K$a|$a(?=$m$b)/$b/s||s/$a/$b/&&++$c;$c}$_=f(1,3).$".f(0,2)

TIO

Nahuel Fouilleul
la source
1

Gelée , 44 36 octets

ŒJfⱮ+€¥Ø.,UŻ¤œịƇþ,¬$¹ƇfƇⱮ`ẎQ$€QƲÐL€Ẉ

Essayez-le en ligne!

Un lien monadique acceptant une liste de listes d'entiers comme argument et renvoyant une liste du nombre d'îlots 1 et 0 dans cet ordre.

Explication

Étape 1

Générer la liste de tous les indices matriciels, chacun avec les indices de son voisin à droite (sauf à droite) et en bas (sauf en bas)

ŒJ            | Multi-dimensional indices (e.g. [1,1],[1,2],[1,3],[2,1],[2,2],[2,3])
      ¥       | Following as as a dyad:
  fⱮ          | - Filter the indices by each of:
    +€      ¤ |   - The indices added to the following
       Ø.     |     - 0,1
         ,U   |     - Paired with itself reversed [0,1],[1,0]
           Ż  |     - Prepended with zero 0,[0,1],[1,0]

Étape 2

Divisez ces indices selon qu'il y avait 1 ou 0 en entrée. Renvoie une liste d'index avec des voisins pour 1s et une autre pour 0s.

  Ƈþ   | Filter each member of the output of stage 1 using the following criteria:
œị   $ | - Corresponding value for the multi-dimensional indices in each of the following as a monad:
   ,¬  |   - The input paired with its inverse

Étape 3

Fusionner des listes avec des membres en nombre commun et en sortie

           ƲÐL€  | For each of the outputs from stage 2, do the following as a monad and repeat until no changes
¹Ƈ               | - Filter out empty lists (only needed on first pass through but included here to save a byte)         
  fƇⱮ`           | - Take each list of indices and filter the list of indices for those containing a match for any of them
        $€       | - For each resulting list of lists:
      Ẏ          |   - Tighten (concatenate top level of lists)
       Q         |   - Uniquify
          Q      | - Uniquify
               Ẉ | Finally output the lengths of the final lists
Nick Kennedy
la source
1

T-SQL 2008, 178 octets

L'entrée est une variable de table.

x et y sont les coordonnées

v est les valeurs 0 et 1 (pourrait également gérer d'autres valeurs numériques)

Les données de test utilisées dans cet exemple:

100
000
001
DECLARE @ table(x int, y int, v int)

INSERT @ values
(1,1,1),(1,2,0),(1,3,0),
(2,1,0),(2,2,0),(2,3,0),
(3,1,0),(3,2,0),(3,3,1)
SELECT*,y-x*99r INTO # FROM @
WHILE @@rowcount>0UPDATE #
SET r=b.r
FROM #,# b
WHERE abs(#.x-b.x)+abs(#.y-b.y)=1and #.v=b.v and #.r>b.r
SELECT v,count(distinct r)FROM #
GROUP BY v

Essayez-le en ligne

t-clausen.dk
la source
1

R , 194 172 octets

function(m,u=!1:2){for(i in 1:2){w=which(m==i-1,T)
N=1:nrow(w)
A=!!N
for(s in N){u[i]=u[i]+A[s]
while(any(s)){A[s]=F
s=c(N[as.matrix(dist(w))[s[1],]==1&A],s[-1])}}}
rev(u)}

Essayez-le en ligne!

Effectuez une recherche en profondeur en commençant dans chaque cellule de la matrice qui est égale à 1 (ou zéro).

  • -2 octets grâce à @Giuseppe
digEmAll
la source