Ein Labyrinth wird als Matrix von Nullen (Wände) und Einsen (begehbarer Raum) in einem beliebigen Format angegeben. Jede Zelle gilt als mit ihren vier (oder weniger) orthogonalen Nachbarn verbunden. Eine verbundene Komponente ist ein Satz von begehbaren Zellen, die alle transitiv miteinander verbunden sind. Ihre Aufgabe ist es, die Schnittpunkte zu identifizieren - begehbare Zellen, die, wenn sie zu Wänden werden, die Anzahl der verbundenen Komponenten verändern würden. Geben Sie nur an diesen Stellen eine boolesche Matrix mit 1-s aus. Das Ziel ist es, dies in den wenigsten Byte Code zu tun.

Die Eingabematrix besteht aus mindestens 3 Zeilen und 3 Spalten. Mindestens eine der Zellen ist eine Wand und mindestens eine ist begehbar. Ihre Funktion oder Ihr Programm muss in der Lage sein, eines der folgenden Beispiele in weniger als einer Minute auf TIO zu verarbeiten weniger als (oder auf Ihrem eigenen Computer, wenn die Sprache von TIO nicht unterstützt wird) zu verarbeiten.

in:
11101001
11011101
00000001
11101111
11110101
00011111
10110001
11111111
out:
01000000
00001001
00000001
00000101
00110000
00010000
00000000
11100000

in:
1111111111111111
1000000000000001
1111111111111101
0000000000000101
1111111111110101
1000000000010101
1011111111010101
1010000001010101
1010111101010101
1010101111010101
1010100000010101
1010111111110101
1010000000000101
1011111111111101
1000000000000001
1111111111111111
out:
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000

in:
1011010001111010
1111111011101101
1110010101001011
1111001110010010
1111010000101001
0111101001000101
0011100111110010
1001110011111110
0101000011100011
1110110101001110
0010100111000110
1000110111011010
0100101000100101
0001010101100011
1001010000111101
1000111011000010
out:
0000000000111010
1011110001001000
0000000000000011
0000000100010000
0000010000101000
0000001000000100
0000000011000000
1001100000011110
0000000001000010
0110100001000110
0000100101000010
1000100000000000
0100001000000100
0000000100100001
0000010000111000
0000010000000010

Stax , 40 Bytes

Çóê↓â.Φ}╞│*w<(♦◙¼ñ£º█¢,D`ì♥W4·☺╛gÇÜ♠╗4D┬

Führen Sie Testfälle aus und debuggen Sie sie

Dieses Programm nimmt Eingaben als durch Leerzeichen getrennte Zeichenfolge entgegen, die Zeilen enthält. Die Ausgabe erfolgt im gleichen Format. Hier ist die entpackte ASCII-Darstellung.

{2%{_xi48&GxG=-}_?m}{'1'2|e{"12|21".22RjMJguHgu%

Die grundlegende Operation zum Zählen einer Insel funktioniert so.

1. Ersetzen Sie die erste '1' durch einen '2'.
2. Regex ersetzen '12|21' durch '22'.
3. Auf Leerzeichen aufteilen.
4. Matrix transponieren.
5. Wiederholen Sie ab 2., bis eine Zeichenfolge wiederholt wird.
6. Wiederholen Sie ab 1., bis '1'die Zeichenfolge kein a mehr enthält . Die Anzahl der Wiederholungen ist die Anzahl der Inseln.

.

{               start map block over input string, composed of [ 01]
  2%            mod by 2. space and 0 yield 0. 1 yields 1. (a)
  {             start conditional block for the 1s.
    _           original char from string (b)
    xi48&       make copy of input with current character replaced with 0
    G           jump to unbalanced }, then return; counts islands (c)
    xG          counts islands in original input (d)
    =           are (c) and (d) equal? 0 or 1 (e)
    -           b - e; this is 1 iff this character is a bridge
  }             end conditional block
  _?            execute block if (a) is 1, otherwise use original char from string
m               close block and perform map over input
}               goto target - count islands and return
{               start generator block
  '1'2|e        replace the first 1 with a 2
  {             start generator block
    "12|21".22R replace "12" and "21" with "22"
    jMJ         split into rows, transpose, and rejoin with spaces
  gu            generate values until any duplicate is encountered
  H             keep the last value
gu              generate values until any duplicate is encountered
%               count number of iterations it took

Bonus 44-Byte-Programm - diese Version gibt im Rasterformat ein und aus.

MATL , 26 Bytes

n:"GG0@(,w4&1ZIuz]=~]vGZye

Die Eingabe ist eine numerische Matrix mit ; als Zeilentrennzeichen verwendet wird.

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

n           % Implicit input: matrix. Push number of elements, N
:           % Range: gives [1 2 ... N]
"           % For each k in [1 2 ... N]
  GG        %   Push input matrix twice
  0@(       %   Write 0 at position k (in column-major order: down, then across).
            %   The stack now contains the original matrix and a modified matrix
            %   with 0 at position k
  ,         %   Do twice
    w       %     Swap
    4       %     Push 4. This specifies 4-element neighbourhood
    &1ZI    %     Label each connected component, using the specified
            %     neighbourhood. This replaces each 1 in the matrix by a
            %     positive integer according to the connected component it
            %     belongs to
    u       %     Unique: gives a vector of deduplicate elements
    z       %     Number of nonzeros. This is the number of connected components
  ]         %   End
  =~        %   Are they different? Gives true of false
]           % End
v           % Concatenate stack into a column vector
GZye        % Reshape (in column-major order) according to size of input matrix.
            % Implicit display

Perl 5 , -p0 105 101 96 93 90 89 Bytes

Verwendet banstelle von1 in der Eingabe.

Stellen Sie sicher, dass die Matrix auf STDIN mit einem Zeilenumbruch abgeschlossen ist

#!/usr/bin/perl -p0
s%b%$_="$`z$'";s:|.:/
/>s#(\pL)(.{@{-}}|)(?!\1)(\pL)#$&|a.$2.a#se&&y/{c/z />0:seg&/\B/%eg

Probieren Sie es online!

Verwendet 3 Substitutionsstufen!

Diese 87-Byte-Version ist sowohl im Eingabe- als auch im Ausgabeformat einfacher zu interpretieren, konkurriert jedoch nicht, da sie drei verschiedene Zeichen in der Ausgabe verwendet:

#!/usr/bin/perl -0p
s%b%$_="$`z$'";s:|.:/
/>s#(\w)(.{@{-}}|)(?!\1)(\w)#$&|a.$2.a#se&&y/{c/z />0:seg&/\B/%eg

Probieren Sie es online!

Es ist einfach, ein weiteres Byte (den regulären Ausdruck) zu speichern s Modifikator) in beiden Versionen indem ein anderes (nicht alphanumerisches) Zeichen als Zeilenabschlusszeichen (anstelle von Zeilenvorschub) verwendet wird. Dadurch ist die Eingabe jedoch wieder ziemlich unlesbar.

Wie es funktioniert

Betrachten Sie die Substitution

s#(\w)(.{columns}|)(?!1)(\w)#c$2c#s

Dies findet zwei Buchstaben, die horizontal oder vertikal nebeneinander liegen und ersetzt sie durch c. In einem Labyrinth, dessen Wege vollständig aus dem Buchstaben bestehen b, passiert nichts, da die Buchstaben gleich sind, aber sobald einer der Buchstaben durch einen anderen ersetzt wird (z. B. z), werden dieser Buchstabe und ein Nachbar durch einen anderen ersetzt, cund die wiederholte Anwendung ist a Fülle die verbundene Komponente mit caus Samenz .

In diesem Fall möchte ich jedoch keine vollständige Überflutung. Ich möchte nur einen der benachbarten Arme ausfüllen z, also möchte ich nach dem ersten Schritt den zverschwunden haben. Das funktioniert bereits mit dem c$2cErsatz, aber ich möchte später eine Überflutung entlang eines anderen Arms ab dem gleichen Punkt neu starten, und ich weiß nicht, welcher der beidenc s ursprünglich zwar. Also benutze ich stattdessen

s#(\w)(.{columns}|)(?!\1)(\w)#$&|a.$2.a#se

b | aist c, b | cist cund z | aist {. In einem Labyrinth mit Pfaden aus bund einem Samen wird zim ersten Schritt bersetzt durch cund zersetzt durch, {der kein Buchstabe ist und nicht übereinstimmt \wund daher keine weiteren Füllungen verursacht. Das wird cjedoch eine weitere Überflutung am Laufen halten und ein Nachbararm des Samens wird gefüllt. ZB ab

  b                      c
  b                      c
bbzbb       becomes    bb{bb
  b                      b
  b                      b

Ich kann dann alles c durch einen Nicht-Buchstaben (zB -) ersetzen und {durch zerneutes ersetzen , um die Überflutung neu zu starten:

  -                      -
  -                      -
bbzbb       becomes    cc{bb
  b                      b
  b                      b

und wiederholen Sie diesen Vorgang, bis alle Nachbarn des Samens konvertiert wurden. Wenn ich dann nochmal {durch ersetze zund fülle:

  -                      -
  -                      -
--z--       stays      --z--
  -                      -
  -                      -

Das z bleibt am Ende zurück, weil es keinen Nachbarn gibt, mit dem man eine Transformation machen kann. Das macht deutlich, was im folgenden Codefragment passiert:

/\n/ >                                    

Finde den ersten Zeilenumbruch. Der Startoffset ist jetzt in@-

s#(\w)(.{@{-}}|)(?!\1)(\w)#$&|a.$2.a#se

Der oben diskutierte reguläre Ausdruck mit @{-}der Anzahl der Spalten (da plain @-den Perl-Parser verwirrt und nicht richtig ersetzt)

&&

Das /\n/gelingt immer und die Substitution ist so lange wahr, wie wir uns noch überfluten können. Der Teil danach &&wird also ausgeführt, wenn die Überflutung eines Arms erfolgt ist. Wenn nicht, ergibt die linke Seite eine leere Zeichenfolge

y/{c/z / > 0

Starten Sie die Überflutung neu und geben Sie 1 zurück, wenn die vorherige Überflutung etwas bewirkt hat. Anderenfalls geben Sie die leere Zeichenfolge zurück. Dieses ganze Stück Code ist darin eingewickelt

s:|.: code :seg

Wenn dies also an einer Startzeichenfolge $_mit einem zan der Startposition ausgeführt wird, wird der darin enthaltene Code mehrmals ausgeführt, wobei meistens nur ein Code zurückgegeben wird, 1wenn ein Nachbararm überflutet wird. Effektiv$_ zerstört und durch so viele ersetzt, 1wie angeschlossene Komponenten vorhanden sindz . Beachten Sie, dass die Schleife bis zur Summe der Komponentengrößen und der Anzahl der Arme ausgeführt werden muss. Dies ist jedoch in Ordnung, da die Anzahl der Zeichen einschließlich der Zeilenumbrüche 2 + 1 beträgt.

Das Labyrinth wird getrennt, wenn keine vorhanden sind 1(leere Zeichenfolge, ein isolierter Scheitelpunkt) oder wenn mehr als 1 Arme vorhanden sind (mehr als 2 1s). Dies kann mit dem regulären Ausdruck überprüft werden /\B/(dies gibt 0anstelle von 1älteren Perl-Versionen. Es ist fraglich, welcher falsch ist). Wenn es nicht passt, wird leider eine leere Zeichenfolge anstelle von angezeigt 0. Dies:|.: code :seg wurde entwickelt , um immer so eine ungerade Zahl zurückgeben , indem Sie ein &mit /\B/diesem geben 0oder 1.

Alles, was übrig bleibt, ist das Gehen des gesamten Eingabearrays und bei jeder begehbaren Position den Samen mit z und Zählen der verbundenen Arme. Das geht ganz einfach mit:

s%b%$_="$`z$'"; code %eg

Das einzige Problem ist, dass in den nicht begehbaren Positionen der alte Wert beibehalten wird. Da wir 0s dort benötigen , bedeutet dies, dass sich das ursprüngliche Eingabearray 0in den nicht begehbaren Positionen befinden muss und in der ursprünglichen Substitution 0übereinstimmt \wund Überschwemmungen auslösen würde. Deshalb verwende ich \pLstattdessen (nur Matchbuchstaben).

Java 8, 503 489 459 455 Bytes

int R,C,v[][];m->{int c[][]=new int[R=m.length][C=m[0].length],r[][]=new int[R][C],i=R*C,t,u;for(;i-->0;)c[t=i/C][u=i%C]=m[t][u];for(;++i<R*C;r[t][u]=i(c)!=i(m)?1:0,c[t][u]=m[t][u])c[t=i/C][u=i%C]=0;return r;}int i(int[][]m){int r=0,i=0,t,u;for(v=new int[R][C];i<R*C;)if(m[t=i/C][u=i++%C]>v[t][u]){d(m,t,u);r++;}return r;}void d(int[][]m,int r,int c){v[r][c]=1;for(int k=-3,t,u;k<4;k+=2)if((t=r+k/2)>=0&t<R&(u=c+k%2-k/2)>=0&u<C&&m[t][u]>v[t][u])d(m,t,u);}

-18 Bytes dank @ceilingcat .

Erläuterung:

Probieren Sie es online aus.

int R,C,                    // Amount of rows/columns on class-level
    v[][];                  // Visited-matrix on class-level

m->{                        // Method with int-matrix as both parameter and return-type
  int c[][]=new int[R=m.length][C=m[0].length],
                            //  Create a copy-matrix, and set `R` and `C`
      r[][]=new int[R][C],  //  Create the result-matrix
      i=R*C,                //  Index-integer
      t,u;                  //  Temp integers
  for(;i-->0;)              //  Loop `i` over each cell:
    c[t=i/C][u=i%C]=m[t][u];//   And copy the values of the input to the copy-matrix
  for(;++i<R*C              //  Loop over the cells again:
      ;                     //    After every iteration:
       r[t][u]=i(c)!=i(m)?  //     If the amount of islands in `c` and `m` are different
        1                   //      Set the current cell in the result-matrix to 1
       :                    //     Else:
        0,                  //      Set it to 0
       c[t][u]=m[t][u])     //     And set the copy-value back again
    c[t=i/C][u=i%C]=0;      //   Change the current value in the copy-matrix to 0
  return r;}                //  Return the result-matrix

// Separated method to determine the amount of islands in a matrix
int i(int[][]m){
  int r=0,                  //  Result-count, starting at 0
      i=0,                  //  Index integer
      t,u;                  //  Temp integers
  for(v=new int[R][C];      //  Reset the visited array
      i<R*C;)               //  Loop over the cells
    if(m[t=i/C][t=i++%C]    //   If the current cell is a 1,
       >v[t][u]){           //   and we haven't visited it yet:
      d(m,i,j);             //    Check every direction around this cell
      r++;}                 //    And raise the result-counter by 1
   return r;}               //  Return the result-counter

// Separated method to check each direction around a cell
void d(int[][]m,int r,int c){
  v[r][c]=1;                //  Flag this cell as visited
  for(int k=-3,u,t;k<4;k+=2)//  Loop over the four directions:
    if((t=r+k/2)>=0&t<R&(u=c+k%2-k/2)>=0&u<C
                            //   If the cell in the direction is within bounds,
       &&m[t][u]            //   and it's a path we can walk,
         >v[t][u])          //   and we haven't visited it yet:
      d(m,i,j);}            //    Do a recursive call for this cell

Python 2 , 290 Bytes

lambda m:[[b([[C and(I,J)!=(i,j)for J,C in e(R)]for I,R in e(m)])!=b(eval(`m`))for j,c in e(r)]for i,r in e(m)]
def F(m,i,j):
	if len(m)>i>=0<=j<len(m[i])>0<m[i][j]:m[i][j]=0;F(m,i,j+1);F(m,i,j-1);F(m,i+1,j);F(m,i-1,j)
b=lambda m:sum(F(m,i,j)or c for i,r in e(m)for j,c in e(r))
e=enumerate

Probieren Sie es online!

-11 Bytes dank Rod
-11 Bytes dank Lynn

Wolfram Language (Mathematica) , 118 Byte

(r=ReplacePart)[0#,Cases[#~Position~1,p_/;(c=Max@MorphologicalComponents[#,CornerNeighbors->1<0]&)@r[#,p->0]>c@#]->1]&

Probieren Sie es online!

Javascript 122 Bytes

Eingabe / Ausgabe als mehrzeiliger String.

m=>m.replace(/./g,(v,p,m,n=[...m],f=p=>n[p]==1&&(n[p]=0,v=f(p-1)+f(p+1)+f(p-w)+f(p+w)-1?1:0,1))=>(f(p),v),w=~m.search`\n`)

Setzen Sie für jede begehbare Zelle einen Block und versuchen Sie, die 4 Nachbarzellen zu füllen. Wenn die aktuelle Zelle kein Schnittpunkt ist, werden alle von einem offenen Nachbarn aus gefüllt. Ansonsten benötige ich mehr als eine Fülloperation, um alle Nachbarzellen zu erreichen.

Weniger golfen

m=>{
  w = m.search('\n') + 1; // offset to the next row
  result = [...m].map( // for each cell
     ( v, // current value
       p  // current position
     ) => {
     n = [...m]; // work on a copy of the input
     // recursive fill function from position p
     // returns 1 if managed to fill at least 1 cell
     fill = (p) => {
        if (n[p] == 1)
        {
           n[p] = 0;
           // flag will be > 1 if the fill from the current point found disjointed areas
           // flag will be 0 if no area could be filled (isolated cell)
           var flag = fill(p+1) + fill(p-1) + fill(p+w) + fill(p-w);
           // v is modified repeatedly, during recursion
           // but I need the value at top level, when fill returns to original caller
           v = flag != 1 ? 1 : 0;
           return 1; // at least 1 cell filled
        }
        else
           return 0; // no fill
     }
     fill(p)
     return v // orginal value or modified by fill function
  }) 
}

Prüfung

var F=
m=>m.replace(/./g,(v,p,m,n=[...m],f=p=>n[p]==1&&(n[p]=0,v=f(p-1)+f(p+1)+f(p-w)+f(p+w)-1?1:0,1))=>(f(p),v),w=~m.search`\n`)

var test=`in:
11101001
11011101
00000001
11101111
11110101
00011111
10110001
11111111
out:
01000000
00001001
00000001
00000101
00110000
00010000
00000000
11100000

in:
1111111111111111
1000000000000001
1111111111111101
0000000000000101
1111111111110101
1000000000010101
1011111111010101
1010000001010101
1010111101010101
1010101111010101
1010100000010101
1010111111110101
1010000000000101
1011111111111101
1000000000000001
1111111111111111
out:
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000

in:
1011010001111010
1111111011101101
1110010101001011
1111001110010010
1111010000101001
0111101001000101
0011100111110010
1001110011111110
0101000011100011
1110110101001110
0010100111000110
1000110111011010
0100101000100101
0001010101100011
1001010000111101
1000111011000010
out:
0000000000111010
1011110001001000
0000000000000011
0000000100010000
0000010000101000
0000001000000100
0000000011000000
1001100000011110
0000000001000010
0110100001000110
0000100101000010
1000100000000000
0100001000000100
0000000100100001
0000010000111000
0000010000000010
`.match(/\d[10\n]+\d/g);
for(i = 0; test[2*i]; ++i)
{
   input = test[2*i]
   check = test[2*i+1]
   result = F(input)
   ok = check == result
   console.log('Test '+ i + ' ' + (ok?'OK':'FAIL'),
   '\n'+input, '\n'+result)
}