Aby znaleźć wyspy 1 i 0 w matrycy

29

Biorąc pod uwagę dwuwymiarową macierz 0 i 1s. Znajdź liczbę wysp dla 1 i 0, gdzie sąsiedzi są tylko w poziomie i pionie.

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 radość
źródło
11
Powinieneś dodać [[1,0];[0,1]]
walizkę testową,
8
Sugeruję, że wyjście może być w dowolnej kolejności, o ile zamówienie jest określone - nie dodaje żadnej wartości do wymuszenia zamówienia
streetster
8
Witamy na stronie!
Arnauld
1
To, na co odpowiedziano w komentarzach, powinno zostać wyjaśnione w treści wyzwania. A dokładniej, jeśli naprawdę chcesz, abyśmy zwrócili 1 przed 0, powinno to być wyraźnie zaznaczone.
Arnauld
4
Sugerowany przypadek testowy: 11111 / 10001 / 10101 / 10001 / 111112 1
Kevin Cruijssen

Odpowiedzi:

16

APL (Dyalog Unicode) , 29 28 bajtów SBCS

-1 dzięki @ Adám

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

Wypróbuj online!

⊂,~∘⊂ matryca i jej negacja

{ dla każdego z nich

⍸⍵ lista par współrzędnych 1s

+/↑|∘.-⍨ macierz odległości manhattan

2> macierz sąsiada

∨.∧⍨⍣≡ zamknięcie przechodnie

≢∪ liczba unikalnych wierszy

ngn
źródło
to jest naprawdę sprytne. czy mógłbyś wyjaśnić, dlaczego gwarantuje się, że ostatnia linia działa - tj. dlaczego unikalne wiersze są równoważne z odpowiedzią. również jest „przechodnia zamknięcia” jest jak na J ^:_?
Jonasz
1
@Jonah patrz czat
ngn
16

J , 57 bajtów

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

Wypróbuj online!

Jest to jeden z tych, w których pomysł jest niewiarygodnie prosty (i myślę, że fajnie), ale wykonanie go miało pewną mechaniczną długość, która maskuje prostotę ... np. Przesunięcie oryginalnej matrycy we wszystkich kierunkach z wypełnieniem 0 jest pełne ((,-)#:i.3) |.!.0 .

Jest prawdopodobne, że tę mechaniczną długość można pograć w golfa i mogę spróbować jutro wieczorem, ale opublikuję sedno tego.

Powiedz, że nasz wkład to:

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

Zaczynamy od macierzy unikalnych liczb całkowitych tego samego rozmiaru:

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

Następnie dla każdej komórki znajdujemy maksimum wszystkich jej sąsiadów i mnożymy przez maskę wejściową:

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

Powtarzamy ten proces, dopóki matryca nie przestanie się zmieniać:

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

A następnie policz liczbę unikalnych, niezerowych elementów. To mówi nam o liczbie 1 wysp.

Stosujemy ten sam proces do „1 minus dane wejściowe”, aby uzyskać liczbę 0 wysp.

Jonasz
źródło
3
Wygląda to bardzo podobnie do mechanizmu „zalewania”, naprawdę porządnie.
Matthieu M.,
7

JavaScript (ES7),  138 ... 107  106 bajtów

Zwraca tablicę [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

Wypróbuj online!

W jaki sposób?

Używamy funkcji rekurencyjnej. Podczas wstępnej rozmowy, szukamy 0 „si 1 ” s. Ilekroć znajdziemy taki punkt początkowy, zwiększamy odpowiedni licznik wysp ( c[0] lub c[1] ) i wchodzimy w fazę rekurencyjną, aby wypełnić obszar podobnych sąsiednich komórek 2 .

Aby zapisać bajty, dokładnie ten sam kod jest używany zarówno dla iteracji root, jak i iteracji rekurencyjnych, ale zachowuje się nieco inaczej.

Podczas pierwszej iteracji:

  • Zaczynamy od V=0,5 dzięki czemu Vv jest zaokrąglane do 0 zarówno dla v=0 i v=1 , dzięki bitowemu OR.
  • X iY są niezdefiniowane, a obliczona ćwiartka(xX)2+(yY)2 obliczana naNaN. Wymusza to niepowodzenie testu nierówności, bez względu na wartość(x,y) .

Podczas iteracji rekurencyjnych:

  • c2c[v ^ 1]++do

Skomentował

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
źródło
Ten kod nie działa dla dużych macierzy, takich jak 100 * 100, z tylko 1s lub 0 z powodu przepełnienia stosu.
KB radość
3
@KBjoy O ile nie określono inaczej w wyzwaniu, naszą domyślną regułą jest to, że nie dbamy o limity implementacji, o ile algorytm bazowy działa teoretycznie dla dowolnego wkładu. ( Oto meta post na ten temat, ale prawdopodobnie jest gdzieś bardziej odpowiedni.)
Arnauld
7

MATL , 14 12 bajtów

,G@-K&1ZIugs

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

,        % 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
źródło
6

K (ngn / k) , 60 55 51 50 46 bajtów

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

Wypróbuj online!

~:\ para danych wejściowych i ich negacja (dosłownie: negate iterate-converge)

{ }' dla każdego

,/x spłaszcz arg

&gdzie są jedynki? - lista indeksów

(0,#*x)\ divmod width (input), aby uzyskać dwie osobne listy dla ys i xs

x-\:'x: odległości między osiami ∆x i ∆y

x*x: wyprostuj je

+/ dodaj ∆x² i ∆y²

2> macierz sąsiada

{|/'x*\:x}/ zamknięcie przechodnie

#? policz unikalne wiersze

ngn
źródło
Po zobaczeniu twojej odpowiedzi cieszę się, że nie próbowałem zmierzyć się z tym w K :)
streetster
2
@streetster haha, dzięki! to nie jest zamierzony efekt :) Chciałbym zachęcić ludzi do nauki (dowolnego dialektu) k i gry w golfa
ngn
6

Wolfram Language (Mathematica) , 64 62 bajtów

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

Wypróbuj online!

Dzięki attinat : możemy pisać 1<0zamiast Falsei zapisywać dwa bajty.

wersja bez gry w golfa:

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

Istnieje oczywiście wbudowana funkcja Mathematica,MorphologicalComponents która pobiera tablicę (lub obraz) i zwraca to samo z pikselami każdej morfologicznie połączonej wyspy zastąpionymi indeksem wysp. Biorąc Maxten wynik daje liczbę wysp (zera tła są pozostawione na zero, a indeks wysp zaczyna się od 1). Musimy to zrobić osobno dla tablicy (podając liczbę 1 wysp) i jeden minus tablicy (podając liczbę 0 wysp). Aby upewnić się, że ukośni sąsiedzi nie liczą się jako sąsiedzi, CornerNeighbors->Falsenależy podać opcję .

rzymski
źródło
-2 bajty, ponieważ nierówności mają wyższy priorytet niżRule
attinat
5

Python 3, 144 127 bajtów

To rozwiązanie wykorzystuje cv2niesamowitą moc przetwarzania obrazu. Pomimo mniej niesamowitych, bardzo długich i czytelnych nazw cv, cv pokonuje obie inne odpowiedzi w języku Python!

Gra w golfa:

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

Rozszerzony:

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
źródło
Nie znam się zbyt dobrze na Pythonie, ale dlaczego potrzebujesz wyraźnych nazw argumentów? Czy to nie tylko 4zamiast connectivity=4i n.uint8zamiast jest dtype=n.uint8możliwe?
Kevin Cruijssen
@KevinCruijssen, potrzebujesz nazw argumentów, jeśli pominiesz argumenty opcjonalne. Przeglądając dokumenty, właściwie nie muszę pomijać, co oszczędza mi dużo bajtów. Dzięki!
Daniel
Ach ok, myślałem, że to coś takiego, ale kiedy tylko spojrzałem na dokumenty, mogłem znaleźć tylko jedną cv2.connectedComponentsmetodę, więc byłem zdezorientowany i pomyślałem, że mógł istnieć inny powód, aby potrzebować nazw argumentów. Jak powiedziałem, nie znam zbyt dobrze Pythona. Wszystko, czego się nauczyłem, pochodzi stąd z CCGC. ;) Ale warto używać nazw zmiennych, aby pominąć inne opcjonalne argumenty.
Kevin Cruijssen
1
Bardzo dobrze! Znalazłem kompilatora online, który zawiera moduł CV2 tutaj .
Jitse
5

J , 46 44 43 bajty

-1 bajt dzięki @miles

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

Wypróbuj online!

testy i ,& -.opakowanie skradzione z odpowiedzi @ jonah

,& -. dla danych wejściowych i ich negacji wykonaj:

4$.$. (y, x) współrzędne 1s jako macierz n × 2

1#.[:|@-"1/~ manhattan odległości: abs (∆x) + abs (∆y)

2> macierz sąsiada

[:+./ .*~^:_: zamknięcie przechodnie

#&~.&( ) liczba unikalnych wierszy

ngn
źródło
1
możesz skomponować długość i unikat, aby zaoszczędzić kolejny bajt, tj. ,&#&~.aby uniknąć limitu[:
mil
@miles dziękuję
ngn
3

Retina 0.8.2 , 155 bajtów

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

Wypróbuj online! Link zawiera przypadek testowy. Wyjaśnienie:

s`1(.*)
;$1a

Jeśli istnieje 1, zmień go na ;i dodaj ana końcu wejścia, aby nie przeszkadzało.

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

Powódź wypełnić kolejne sąsiednie 1litery ;s.

}

Powtarzaj, aż wszystkie wyspy 1s zostaną zamienione w ;s.

s`0(.*)
:$1b

Jeśli istnieje 0, zmień go na :i dodaj bna końcu wejścia, aby nie przeszkadzało.

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

Powódź wypełnić kolejne sąsiednie 0litery :s.

}

Powtarzaj, aż wszystkie wyspy 0s zostaną zamienione w :s.

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

Osobno policz liczbę wysp 1s i 0s.

Neil
źródło
3

Haskell , 228 227 225 224 bajtów

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

Wypróbuj online!

Wyjaśnienie:

Pomysł na to rozwiązanie jest następujący: Zainicjuj macierz unikalnymi wartościami w każdej komórce, dodatnimi 1i ujemnymi dla 0. Następnie kilkakrotnie porównaj każdą komórkę z sąsiadami i, jeśli sąsiad ma ten sam znak, ale liczbę o większej wartości bezwzględnej, zamień numer komórki na numer sąsiada. Gdy osiągnie to ustalony punkt, policz liczbę odrębnych liczb dodatnich dla liczby 1regionów i wyraźnych liczb ujemnych dla liczby regionów0 regionów.

W kodzie:

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

można podzielić na przetwarzanie wstępne (przypisywanie liczb do komórek), iterację i przetwarzanie końcowe (zliczanie komórek)

Przetwarzanie wstępne

Część wstępnego przetwarzania jest funkcją

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

Który używa zjako skrótu zipWithdo golenia kilku bajtów. To, co tu robimy, to spakowanie dwuwymiarowej tablicy z indeksami liczb całkowitych w wierszach i nieparzystymi indeksami liczb całkowitych w kolumnach. Robimy to, ponieważ możemy zbudować unikalną liczbę całkowitą z pary liczb całkowitych (i,j)przy użyciu formuły (2^i)*(2j+1). Jeśli generujemy tylko nieparzyste liczby całkowite j, możemy pominąć obliczanie 2*j+1, oszczędzając trzy bajty.

Dzięki unikalnemu numerowi musimy teraz tylko pomnożyć znak w oparciu o wartość w macierzy, która jest uzyskiwana jako 2*x-1

Iteracja

Iteracja jest wykonywana przez

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

Ponieważ dane wejściowe są w postaci listy list, przeprowadzamy porównanie sąsiadów w każdym wierszu, transponujemy macierz, ponownie wykonujemy porównanie w każdym wierszu (który ze względu na transpozycję było to, co było wcześniej w kolumnach) i transponujemy ponownie. Kod, który wykonuje jeden z tych kroków, to

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

gdzie ljest funkcja porównawcza (wyszczególniona poniżej) i transpose.map lwykonuje połowę kroków porównania i transpozycji. (.)>>=idwykonuje argument dwa razy, ponieważ \f -> f.fw tym przypadku jest on pozbawiony punktów i o jeden bajt krótszy ze względu na reguły pierwszeństwa operatora.

ljest zdefiniowany w powyższym wierszu jako l x=z(!)(z(!)x(0:x))$tail x++[0]. Ten kod wykonuje operator porównania (!)(patrz poniżej) na każdej komórce, najpierw z lewym sąsiadem, a następnie z prawym sąsiadem, poprzez skompresowanie listy xza pomocą listy przesuniętej w prawo 0:xi listy przesuniętej w lewotail x++[0] w lewo. Używamy zer do wypełniania przesuniętych list, ponieważ nigdy nie mogą wystąpić w macierzy wstępnie przetworzonej.

a!bjest zdefiniowany w wierszu powyżej tego jako a!b=div(max(a*a)(a*b))a. To, co chcemy tutaj zrobić, to następujące rozróżnienie wielkości liter:

  • Jeśli sgn(a) = -sgn(b)mamy dwa przeciwstawne obszary w macierzy i nie chcemy ich ujednolicać, więc apozostaje niezmienione
  • Jeśli sgn(b) = 0mamy skrzynkę narożną, w której bznajduje się wypełnienie, a zatem apozostaje niezmieniona
  • Jeśli sgn(a) = sgn(b)chcemy ujednolicić oba obszary i przyjąć ten o większej wartości bezwzględnej (dla wygody).

Zauważ, że sgn(a)nigdy nie będzie 0. Osiągamy to dzięki podanej formule. Jeśli znaki ai bróżnią się, a*bjest mniejsze lub równe zero, a a*azawsze jest większe od zera, więc wybieramy je jako maksimum i dzielimy z, aaby wrócić a. W przeciwnym razie max(a*a)(a*b)jest abs(a)*max(abs(a),(abs(b))i dzieląc to przeza , otrzymujemy sgn(a)*max(abs(a),abs(b)), co jest liczbą o większej wartości bezwzględnej.

Aby iterować funkcję, ((.)>>=id$transpose.map l)dopóki nie osiągnie ustalonego punktu, używamy (until=<<((==)=<<)), który jest wzięty z tej odpowiedzi przepełnienia stosu .

Przetwarzanie końcowe

Do przetwarzania końcowego używamy tej części

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

który jest tylko zbiorem kroków.

(>>=id)zgniata listę list w jedną listę, nubpozbywa się dubletów, (\x->length.($x).filter<$>[(>0),(<0)])dzieli listę na parę list, jedną na liczby dodatnie i jedną na liczby ujemne, i oblicza ich długości.

Sacchan
źródło
2

Java 10, 359 355 281 280 261 246 bajtów

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 bajty dzięki @NahuelFouilleul .

Wypróbuj online.

Wyjaśnienie:

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
źródło
1
-74 bajty , usuwanie klonu i używanie |=2: 0 -> 2 i 1 -> 3, jednak >0zmieniono na==1
Nahuel Fouilleul
przepraszam, że musiałem usunąć testy, aby link tio zmieścił się w komentarzach
Nahuel Fouilleul
@NahuelFouilleul Dzięki, sprytne korzystanie |=2! I nadal mógłbym użyć <2zamiast ==1bajtu -1, najpierw sprawdzając 0(i dlatego są one zmieniane na 2, a następnie za pomocą <2sprawdzania 1(które są zmieniane na 3))
Kevin Cruijssen
2

Python 3 , 167 bajtów

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)

Wypróbuj online!


Python 2 , 168 bajtów

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

Wypróbuj online!

-2 bajty dzięki Kevin Cruijssen

Poprawka formatowania 2 bajtów

Wyjaśnienie

Licznik jest przechowywany przez 0 i 1 s. Dla każdego wpisu w macierzy wykonywane są następujące działania:

  • Zwiększ licznik dla bieżącej wartości o 1
  • Jeśli ta sama wartość istnieje bezpośrednio powyżej lub w lewo, zmniejsz o 1

To daje wynik fałszywie dodatni dla przypadków wyrównanych do lewej, takich jak

0 0 1
1 1 1

lub

0 1
1 1

W takiej sytuacji licznik zmniejsza się o 1.

Zwracana wartość to [#1, #0]

Jitse
źródło
1
Obawiam się, że OP, o którym mowa w drugim komentarzu, powinna być taka [#1, #0]. Trochę bezsensownego imo, aby to egzekwować, ale na razie to jest to. W każdym razie, można Golf {not c}do {c^1}i rozwiązać problem wspomniałem zmieniając n[c]+=się n[c^1]+=w podobnej sprawie. Dobra odpowiedź, +1 ode mnie. :)
Kevin Cruijssen
Ach, masz rację. Dzięki!
Jitse
1

Perl 5 ( -0777p), 110 bajtów

Może być ulepszona, używa regex do zastąpienia 1z 3, następnie 0z 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
źródło
1

Galaretka , 44 36 bajtów

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

Wypróbuj online!

Link monadyczny przyjmujący listę argumentów liczb całkowitych jako argument i zwracający listę liczby wysp 1 i 0 w tej kolejności.

Wyjaśnienie

Krok 1

Wygeneruj listę wszystkich indeksów macierzowych, każdy z indeksami sąsiada po prawej stronie (chyba że po prawej stronie) i w dół (chyba że na dole)

Œ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]

Krok 2

Podziel te wskaźniki według tego, czy na wejściu było 1 czy 0. Zwraca jedną listę indeksów z sąsiadami dla 1s, a drugą dla 0.

  Ƈþ   | 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

Krok 3

Scal listy z elementami wspólnymi i licznikami wyjściowymi

           ƲÐ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
źródło
1

T-SQL 2008, 178 bajtów

Dane wejściowe to zmienna tabelowa.

xiy są współrzędnymi

v to wartości 0 i 1 (może również obsługiwać inne wartości liczbowe)

Dane testowe użyte w tym przykładzie:

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

Wypróbuj online

t-clausen.dk
źródło
1

R , 194 172 bajtów

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

Wypróbuj online!

Wykonaj wyszukiwanie od pierwszej głębokości, zaczynając od każdej komórki macierzy, która jest równa 1 (lub zero).

  • -2 bajty dzięki @Giuseppe
digEmAll
źródło