Un labyrinthe est donné sous la forme d'une matrice de 0 (murs) et de 1 (espace accessible à pied) dans n'importe quel format pratique. Chaque cellule est considérée comme connectée à ses 4 voisins orthogonaux (ou moins). Un composant connecté est un ensemble de cellules accessibles à pied toutes connectées de manière transitoire les unes aux autres. Votre tâche consiste à identifier les points de coupure - des cellules praticables qui, si elles étaient transformées en murs, changeraient le nombre de composants connectés. Générez une matrice booléenne avec 1-s uniquement à ces emplacements. Le but est de le faire dans le moins d'octets de code.

La matrice d'entrée comprendra au moins 3 lignes et 3 colonnes. Au moins une de ses cellules sera un mur et au moins une sera accessible à pied. Votre fonction ou programme doit pouvoir traiter l'un des exemples ci-dessous en moins d'une minute sur TIO (ou sur votre propre ordinateur, si la langue n'est pas prise en charge par 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 octets

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

Exécuter et déboguer des cas de test

Ce programme prend l'entrée comme une chaîne séparée par des espaces contenant des lignes. La sortie est au même format. Voici la représentation ascii non emballée.

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

L'opération fondamentale pour compter une île fonctionne comme ceci.

1. Remplacez le premier '1'par un '2'.
2. Regex remplacer '12|21'par '22'.
3. Split sur les espaces.
4. Transposer la matrice.
5. Répétez de 2. jusqu'à ce qu'une chaîne soit répétée.
6. Répétez de 1. jusqu'à ce qu'il n'y ait plus de a '1'dans la chaîne. Le nombre de répétitions est le nombre d'îles.

.

{               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

Programme bonus de 44 octets - cette version entre et sort en utilisant le format de grille.

MATL , 26 octets

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

L'entrée est une matrice numérique, utilisant ;comme séparateur de ligne.

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

Explication

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 octets

Utilise bau lieu de1 dans l'entrée.

Assurez-vous que la matrice sur STDIN se termine par une nouvelle ligne

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

Essayez-le en ligne!

Utilise 3 niveaux de substitution!

Cette version de 87 octets est à la fois au format d'entrée et de sortie plus facile à interpréter, mais n'est pas en concurrence car elle utilise 3 caractères différents dans la sortie:

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

Essayez-le en ligne!

Il est facile d'enregistrer un autre octet (l'expression rationnelle s modificateur d' régulière) dans les deux versions en utilisant un caractère différent (non alphanumérique) comme terminateur de ligne (au lieu de la nouvelle ligne), mais cela rend à nouveau l'entrée assez illisible.

Comment ça fonctionne

Considérez la substitution

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

Cela trouvera deux lettres différentes et côte à côte horizontalement ou verticalement et les remplacera par c. Dans un labyrinthe dont les chemins sont entièrement constitués de la lettre, brien ne se passera car les lettres sont les mêmes, mais dès qu'une des lettres est remplacée par une autre (par exemple z), cette lettre et un voisin seront remplacés cet une application répétée est un inondation du composant connecté avec cde la semence z.

Dans ce cas, je ne veux cependant pas un remplissage complet. Je veux remplir un seul des bras voisins z, donc après la première étape, je veux qu'ils zdisparaissent. Cela fonctionne déjà avec le c$2cremplacement, mais plus tard, je veux redémarrer un remplissage d'inondation le long d'un autre bras à partir du même point et je ne sais plus lequel des cs était à l'origine z. Donc à la place j'utilise

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

b | aest c, b | cest cet z | aest {. Donc, dans un labyrinthe avec des chemins composés bet une graine zdans la première étapeb sera remplacée par cet zsera remplacée par {ce qui n'est pas une lettre et ne correspond pas \wet ne provoquera donc pas de remplissages supplémentaires. Le ccependant gardera un nouveau remplissage d'inondation aller et un bras voisin de la graine est rempli. Par exemple à partir de

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

Je peux ensuite remplacer tous les c par des non-lettres (par exemple -) et les remplacer {à znouveau pour redémarrer le remplissage:

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

et répétez ce processus jusqu'à ce que tous les voisins de la graine aient été convertis. Si je remplace ensuite {par zet remplit:

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

Le zreste reste à la fin car il n'y a pas de voisin avec qui faire une transformation. Cela montre clairement ce qui se passe dans le fragment de code suivant:

/\n/ >                                    

Trouvez la première nouvelle ligne. Le décalage de départ est maintenant@-

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

L'expression régulière discutée ci-dessus avec @{-}comme nombre de colonnes (puisque plain@- confond l'analyseur perl et ne le remplace pas correctement)

&&

Le /\n/réussit toujours et la substitution est vraie tant que nous pouvons encore remplir. Donc la partie après&& est exécutée si le remplissage d'un bras est effectué. Sinon, le côté gauche correspond à une chaîne vide

y/{c/z / > 0

Redémarrez le remplissage et retournez 1 si le remplissage précédent a fait quelque chose. Sinon, retourne la chaîne vide. Tout ce morceau de code est enveloppé à l'intérieur

s:|.: code :seg

Donc, si cela est exécuté sur une chaîne de départ $_avec un zà la position de départ, le morceau de code à l'intérieur sera exécuté plusieurs fois, la plupart du temps, ne retournant rien, mais à 1chaque fois qu'un bras voisin est rempli. Effectivement$_ détruit et remplacé par autant de 1s qu'il y a de composants connectés z. Notez que la boucle doit être exécutée jusqu'à la somme des tailles des composants + nombre de fois d'armements mais c'est OK car il y aura "nombre de caractères y compris les sauts de ligne * 2 + 1" fois.

Le labyrinthe se déconnecte s'il n'y en a pas 1(chaîne vide, sommet isolé) ou s'il y a plus de 1 bras (plus de 2 1s). Cela peut être vérifié en utilisant l'expression régulière /\B/(cela donne 0au lieu de 1sur les anciennes versions de Perl. On peut dire laquelle est fausse). Malheureusement, s'il ne correspond pas, cela donnera une chaîne vide au lieu de 0. Cependant, le a s:|.: code :segété conçu pour toujours renvoyer un nombre impair donc en faisant un &avec /\B/cela donnera 0ou 1.

Il ne reste plus qu'à parcourir l'ensemble du réseau d'entrée et à chaque position de marche avec zet compter les bras connectés. Cela se fait facilement avec:

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

Le seul problème est que dans les positions non accessibles à pied, l'ancienne valeur est conservée. Puisque nous avons besoin de 0s, cela signifie que le tableau d'entrée d'origine doit avoir 0dans les positions non accessibles et 0correspond \wdans la substitution d'origine et déclencherait des remplissages. C'est pourquoi j'utilise à la \pLplace (uniquement des lettres de correspondance).

Java 8, 503 489 459 455 octets

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 octets grâce à @ceilingcat .

Explication:

Essayez-le en ligne.

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 octets

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

Essayez-le en ligne!

-11 octets grâce à Rod
-11 octets grâce à Lynn

Wolfram Language (Mathematica) , 118 octets

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

Essayez-le en ligne!

Javascript 122 octets

Entrée / sortie sous forme de chaîne multiligne.

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

Pour chaque cellule accessible à pied, mettez un bloc et essayez de remplir les 4 cellules voisines. Si la cellule actuelle n'est pas un point de coupure, le démarrage à partir de n'importe quel voisin ouvert les remplira tous. Sinon, j'ai besoin de plus d'une opération de remplissage pour atteindre toutes les cellules voisines.

Moins golfé

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

Tester

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