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

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 / 11111→2 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


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.


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 V−v jest zaokrąglane do 0 zarówno dla v=0 i v=1 , dzięki bitowemu OR.
  • X iY są niezdefiniowane, a obliczona ćwiartka(x−X)2+(y−Y)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

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)

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


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


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

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


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.


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.


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

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]


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


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

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


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
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.