Um labirinto é dado como uma matriz de 0s (paredes) e 1s (espaço acessível) em qualquer formato conveniente. Cada célula é considerada conectada aos seus 4 (ou menos) vizinhos ortogonais. Um componente conectado é um conjunto de células passáveis, todas conectadas transitivamente umas às outras. Sua tarefa é identificar os pontos de corte - células acessíveis que, se transformadas em paredes, alterariam o número de componentes conectados. Saída de uma matriz booleana com 1 s apenas nesses locais. O objetivo é fazê-lo com o menor número de bytes de código.

A matriz de entrada consistirá em pelo menos 3 linhas e 3 colunas. Pelo menos uma de suas células será uma parede e pelo menos uma poderá ser percorrida. Sua função ou programa deve poder processar qualquer um dos exemplos abaixo em menos de um minuto no TIO (ou no seu próprio computador, se o idioma não for suportado pelo TIO).

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┬

Executar e depurar casos de teste

Este programa recebe entrada como uma sequência separada por espaços, contendo linhas. A saída está no mesmo formato. Aqui está a representação ascii descompactada.

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

A operação fundamental para contar uma ilha funciona assim.

1. Substitua o primeiro '1'por a '2'.
2. Regex substitua '12|21'por '22'.
3. Dividir em espaços.
4. Matriz de transposição.
5. Repita de 2. até que uma sequência seja repetida.
6. Repita de 1. até que não haja mais a '1'na string. O número de repetições é o número de ilhas.

.

{               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

Programa de 44 bytes de bônus - esta versão entra e sai usando o formato de grade.

MATL , 26 bytes

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

A entrada é uma matriz numérica, usando ;como separador de linhas.

Experimente online! Ou verifique todos os casos de teste .

Explicação

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

Usa em bvez de 1na entrada.

Verifique se a matriz no STDIN é finalizada com uma nova linha

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

Experimente online!

Usa 3 níveis de substituição!

Esta versão de 87 bytes é mais fácil de interpretar nos formatos de entrada e saída, mas não está competindo, pois usa 3 caracteres diferentes na saída:

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

Experimente online!

É fácil salvar outro byte (o smodificador regex ) nas duas versões usando algum caractere diferente (não alfanumérico) como terminador de linha (em vez de nova linha), mas isso torna a entrada bastante ilegível novamente.

Como funciona

Considere a substituição

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

Ele encontrará duas letras diferentes e próximas umas das outras na horizontal ou na vertical e as substituirá por c. Em um labirinto cujos caminhos consistem inteiramente na letra, bnada acontecerá, pois as letras são as mesmas, mas assim que uma das letras for substituída por outra (por exemplo z), essa letra e um vizinho serão substituídos por cuma aplicação repetida. inundação do componente conectado com a cpartir da semente z.

Neste caso, no entanto, não quero um preenchimento completo. Eu quero preencher apenas um dos braços vizinhos z, então, após o primeiro passo, quero zir embora. Isso já funciona com a c$2csubstituição, mas depois pretendo reiniciar um preenchimento de inundação ao longo de outro braço, começando do mesmo ponto e não sei mais qual deles cera originalmente z. Então, ao invés, eu uso

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

b | aé c, b | cé ce z | aé {. Assim, em um labirinto com caminhos compostos be uma semente zno primeiro passo bserá substituída ce zsubstituída pela {que não é uma letra e não corresponde \we, portanto, não causará preenchimentos adicionais. No centanto, isso manterá um novo preenchimento de inundação e um braço vizinho da semente será preenchido. Por exemplo, começando de

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

Posso, então, substituir todos os c por alguns carta não (por exemplo -) e substitua {por zoutra vez para reiniciar a inundação-fill:

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

e repita esse processo até que todos os vizinhos da semente tenham sido convertidos. Se eu substituir novamente {por ze preencher:

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

Os zrestos ficam para trás no final, porque não há vizinho com quem fazer uma transformação. Isso deixa claro o que acontece no seguinte fragmento de código:

/\n/ >                                    

Encontre a primeira nova linha. O deslocamento inicial está agora em@-

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

O regex discutido acima com @{-}o número de colunas (uma vez que plain @-confunde o analisador perl e não o substitui adequadamente)

&&

O /\n/sempre é bem-sucedido e a substituição é verdadeira desde que ainda possamos inundar. Portanto, a parte seguinte &&é executada se o preenchimento de um braço for concluído. Caso contrário, o lado esquerdo é avaliado como uma sequência vazia

y/{c/z / > 0

Reinicie o preenchimento e retorne 1 se o preenchimento anterior tiver feito alguma coisa. Caso contrário, retorne a string vazia. Todo esse código está envolvido

s:|.: code :seg

Portanto, se isso for executado em uma string inicial $_com a zna posição inicial, o código dentro será executado muitas vezes retornando nada, mas 1sempre que um braço vizinho for inundado. Efetivamente $_é destruído e substituído por tantos 1s quantos componentes conectados estiverem conectados z. Observe que o loop precisa ser executado até a soma dos tamanhos dos componentes + número de vezes de armas, mas isso é bom, pois ele "número de caracteres, incluindo novas linhas * 2 + 1" vezes.

O labirinto é desconectado se não houver 1(corda vazia, um vértice isolado) ou se houver mais de 1 braço (mais de 2 1s). Isso pode ser verificado usando o regex /\B/(isso fornece, em 0vez de 1versões perl mais antigas. É discutível qual deles está errado). Infelizmente, se não corresponder, isso dará uma string vazia em vez de 0. No entanto, o s:|.: code :segfoi projetado para sempre retornar um número ímpar, fazendo um &com /\B/isso dará 0ou 1.

Tudo o que resta é caminhar por toda a matriz de entrada e, em cada posição caminhável, semear ze contar os braços conectados. Isso é feito facilmente com:

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

O único problema é que nas posições não passíveis de passagem o valor antigo é mantido. Como precisamos de 0s lá, isso significa que a matriz de entrada original deve ter 0nas posições não passíveis de passagem e 0correspondências \wna substituição original e provocaria enchentes. É por isso que eu uso \pL(apenas as letras correspondentes).

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 graças a @ceilingcat .

Explicação:

Experimente online.

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

Experimente online!

-11 bytes graças a Rod
-11 bytes graças a Lynn

Wolfram Language (Mathematica) , 118 bytes

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

Experimente online!

Javascript 122 bytes

Entrada / saída como uma sequência multilinha.

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

Para cada célula passável, coloque um bloco e tente preencher as 4 células vizinhas. Se a célula atual não for um ponto de corte, a partir de qualquer vizinho aberto preencherá todos eles. Senão, precisarei de mais de uma operação de preenchimento para alcançar todas as células vizinhas.

Menos golfe

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

Teste

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