Точки в лабиринте

13

Лабиринт задается в виде матрицы 0 (стены) и 1 (пройденное пространство) в любом удобном формате. Каждая ячейка считается связанной со своими 4 (или менее) ортогональными соседями. Подключенный компонент представляет собой набор проходимых клеток все транзитивно соединенных друг с другом. Ваша задача - определить точки среза - проходные ячейки, которые, если превратиться в стены, изменит количество подключенных компонентов. Выведите логическую матрицу с 1-й только в этих местах. Цель состоит в том, чтобы сделать это с наименьшим количеством байтов кода.

Входная матрица будет состоять как минимум из 3 строк и 3 столбцов. По крайней мере одна из его клеток будет стеной, и по крайней мере одна будет проходной. Ваша функция или программа должны быть в состоянии обработать любой из приведенных ниже примеров в течение минуты на TIO (или на вашем собственном компьютере, если язык не поддерживается 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
code-golf graph-theory maze binary-matrix СПП
источник
так, найдите все мосты во всех подграфах
HyperNeutrino
1
Я думаю, что задача выиграет от пошагового примера для меньшей матрицы.
г-н Xcoder
1
@HyperNeutrino мост - это что-то другое - это ребро (а не вершина), удаление которого увеличивает количество связанных компонентов
ngn
1
@HyperNeutrino также, подграф не совсем совпадает с подключенным компонентом
ngn
1
@Notatree Ты прав. Я допустил ошибку. Сейчас уже поздно это исправлять, но я надеюсь, что это не испортит веселье.
NNN

Ответы:

3

Stax , 40 байт

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

Запуск и отладка тестовых случаев

Эта программа принимает ввод как разделенную пробелами строку, содержащую строки. Вывод в том же формате. Вот распакованное представление ascii. 

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

Основная операция для подсчета острова работает следующим образом.

  1. Заменить первое '1'на '2'.
  2. Regex заменить '12|21'на '22'.
  3. Сплит на пространствах.
  4. Транспонировать матрицу.
  5. Повторяйте от 2. до тех пор, пока строка не будет повторена.
  6. Повторяйте от 1. до тех пор, пока '1'в строке больше не будет a . Количество повторений - это количество островов.

,

{               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

Бонусная 44-байтовая программа - эта версия вводит и выводит, используя формат сетки.

рекурсивный
источник
это обрабатывает второй пример менее чем за минуту на вашем компьютере?
нг
@ngn: он делает все три примера в 41-м на этом ноутбуке среднего класса в Chrome. Также я просто исправил основную ссылку. Я случайно оставил его на более старой нерабочей версии.
рекурсивный
3

MATL , 26 байт

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

Ввод представляет собой числовую матрицу, используя в ;качестве разделителя строк.

Попробуйте онлайн! Или проверьте все тестовые случаи .

объяснение

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
Луис Мендо
источник
2

Perl 5 , -p0 105 101 96 93 90 89 байт

Используется bвместо 1ввода.

Убедитесь, что матрица на STDIN завершена с новой строки

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

Попробуйте онлайн!

Использует 3 уровня замещения!

Эта 87-байтовая версия и во входном, и в выходном формате проще для интерпретации, но не конкурирует, поскольку в выводе используются 3 разных символа:

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

Попробуйте онлайн!

Легко сохранить другой байт ( sмодификатор regex ) в обеих версиях, используя какой-либо другой (не буквенно-цифровой) символ в качестве разделителя строк (вместо новой строки), но это делает ввод снова совершенно нечитаемым.

Как это устроено

Рассмотрим замену 

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

Это позволит найти две разные буквы, расположенные рядом друг с другом по горизонтали или вертикали, и заменить их на c. В лабиринте, пути которого состоят полностью из буквы, bничего не произойдет, так как буквы одинаковы, но как только одна из букв будет заменена другой (например, zэта буква и сосед будут заменены, cи повторное применение будет заливка подключенного компонента cиз семян z.

Однако в этом случае я не хочу полной заливки. Я хочу заполнить только одно соседнее оружие z, поэтому после первого шага хочу zуйти. Это уже работает с c$2cзаменой, но позже я хочу перезапустить заливку вдоль другой руки, начиная с той же точки, и я не знаю, какой из cs был zбольше. Так что вместо этого я использую

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

b | aесть c, b | cесть cи z | aесть {. Таким образом , в лабиринте с дорожками, состоящими из bи семеите zна первом этапе bбудет получать заменены cи zполучите заменены {что не буква и не соответствует , \wи поэтому не будет причиной дальнейших заливок. cОднако будет продолжать дальнейший Flood-заливку собирается и один сосед руки семени заполняется. Например, начиная с

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

Затем я могу заменить все с на некоторых не буквы (например -) и заменить {на zеще раз , чтобы перезапустить Flood-заливку:

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

и повторяйте этот процесс, пока все соседи семени не будут обращены. Если бы я тогда еще раз заменить {на zи наводнения заполнения:

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

В zостается за в конце , потому что нет соседей , чтобы сделать преобразование с. Это проясняет, что происходит в следующем фрагменте кода:

/\n/ >

Найдите первую новую строку. Начальное смещение теперь в@-

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

Вышеуказанное регулярное выражение с @{-}числом столбцов (так как plain @-путает парсер perl и не заменяет его должным образом)

&&

/\n/Всегда преуспевает и замена верна до тех пор , как мы можем все еще наводнение заполнения. Таким образом, часть после &&выполняется, если заполнение одной руки выполнено. Если нет, то левая сторона вычисляется как пустая строка

y/{c/z / > 0

Перезапустите заливку и верните 1, если предыдущая заливка что-то сделала. В противном случае верните пустую строку. Весь этот кусок кода обернут внутри

s:|.: code :seg

Таким образом, если это выполняется для начальной строки $_с zначальной позицией, то фрагмент кода внутри будет выполняться много раз, в основном, ничего не возвращая, кроме как 1каждый раз, когда соседняя ветвь заполняется. Эффективно $_уничтожается и заменяется столько же, 1сколько подключенных компонентов z. Обратите внимание, что цикл должен быть выполнен с точностью до суммы размеров компонентов + количества тактов, но это нормально, так как он будет «количество символов, включая переводы строки * 2 + 1».

Лабиринт отключается, если нет ни одного 1(пустая строка, изолированная вершина) или если имеется более 1 руки (более 2 1с). Это можно проверить с помощью регулярного выражения /\B/(это дает 0вместо 1старых версий Perl. Можно утверждать, что это не так). К сожалению, если он не совпадает, вместо него выдается пустая строка 0. Однако он s:|.: code :segбыл разработан, чтобы всегда возвращать нечетное число, поэтому, сделав &с /\B/этим, вы получите 0или 1.

Все, что осталось, - это пройти весь входной массив и в каждой проходной позиции начать с zподсчета и подключенных рук. Это легко сделать с помощью:

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

Единственная проблема заключается в том, что в неприступных позициях сохраняется старое значение. Так как нам нужно 0s, это означает, что исходный входной массив должен находиться 0в непригодных для прохода позициях и 0совпадениях \wв исходной замене и вызывать заливки. Вот почему я использую \pLвместо этого (только совпадающие буквы).

Тон Хоспел
источник
2

Ява 8, 503 489 459 455 байт

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 байт благодаря @ceilingcat .

Объяснение:

Попробуйте онлайн.

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
Кевин Круйссен
источник
1

Python 2 , 290 байт

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

Попробуйте онлайн!

-11 байт благодаря Роду
-11 байт благодаря Линн

HyperNeutrino
источник
1
Короче использовать F(m,i,j)для каждого элемента, экономя 11 байтов
Rod
for q in((i,j+1),(i,j-1),(i+1,j),(i-1,j)):-> for q in(i,j+1),(i,j-1),(i+1,j),(i-1,j):- rm внешние
парены
Поскольку Fнеявно возвращает None, вы можете использовать F(m,i,j)or cвместо [F(m,i,j)]and c.
Линн
Также and m[i][j]может быть >0<m[i][j]и [q[:]for q in m]может быть eval(`m`).
Линн
@ Линн, ты имеешь в виду eval ('m')? не вернет ли это тот же экземпляр списка?
ноября
1

Javascript 122 байта

Ввод / вывод в виде многострочной строки.

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

Для каждой клетки, которую можно пройти, поместите блок и попробуйте заполнить 4 соседние клетки. Если текущая ячейка не является точкой обрезки, то, начиная с любого открытого соседа, все они будут заполнены. Иначе мне понадобится более одной операции заполнения, чтобы добраться до всех соседних ячеек.

Меньше гольфа

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

Тестовое задание 

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)
}
Развернуть фрагмент

edc65
источник