Вызов

По графическому вводу фигуры определите, сколько в ней отверстий.

Не дублировать

Этот вопрос был отмечен как возможный дубликат Графских островов . Я считаю, что эта задача отличается от задачи на Острове Графов, потому что в этой вы должны выяснить, как устранить блоки, которые касаются границы.

вход

Входные данные будут представлены в виде двухмерной формы ввода: многострочная строка, массив строк или массив символьных массивов. Это представляет форму. Форма гарантированно будет только в одной части, соединенной ребром. Пожалуйста, укажите, как вы хотите, чтобы ввод был принят.

Выход

Выход - одно целое число, указывающее, сколько отверстий в форме. Разрешающий символ новой строки разрешен, но нет других начальных или конечных пробелов. Другими словами, выходные данные должны соответствовать регулярному выражению ^\d+\n?$.

Что такое дыра?

Это одиночные отверстия:

####
#  #
#  #
####

####
#  #
# ##
###

#####
# # #
#   #
#####

Это не дыры:

########
########
#   ####
#   ####
# ######
#       
########

###
#  
###

##########
#         
# ########
# #      #
# # #### #
# #   ## #
# ###### #
#        #
##########

В значительной степени, если этот промежуток соединяется с внешним краем, это не дыра.

Контрольные примеры

#####
# # # -> 2
#####

#####
#    
# ### -> 1
# # #
#####

####
## # -> 1 (things are connected by edges)
# ##
####

###
### -> 0 (You must handle shapes with no holes, but input will always contain at least one filled space)
###

Вы можете использовать любой символ вместо «#» и вместо пробелов.

Критерии объективной оценки

Оценка дается как количество байтов в вашей программе.

выигрыш

Победитель будет представлен с самым низким счетом, к 4 апреля.

MATLAB / Octave, 18 байт

@(g)1-bweuler(g,4)

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

Это анонимная функция, принимающая логическую матрицу в качестве входных данных. Объект формируется из trueзаписей (с указанным подключением), пустое пространство - это falseзаписи.

bweuler затем вычисляет число Эйлера двоичного изображения, представленного этой матрицей, то есть количество объектов минус число отверстий.

Mathematica, 59 57 байт

1/.ComponentMeasurements[#,"Holes",CornerNeighbors->0>1]&

Для этого есть встроенная функция. Вводит в виде 2D матрицы1 s (стены) и 0s (отверстия). Для удобства вот все тестовые примеры в этом формате ввода:

{{{1,1,1,1},{1,0,0,1},{1,0,0,1},{1,1,1,1}},
 {{1,1,1,1},{1,0,0,1},{1,0,1,1},{1,1,1,0}},
 {{1,1,1,1,1},{1,0,1,0,1},{1,0,0,0,1},{1,1,1,1,1}},
 {{1,1,1,1,1,1,1,1},{1,1,1,1,1,1,1,1},{1,0,0,0,1,1,1,1},{1,0,0,0,1,1,1,1},{1,0,1,1,1,1,1,1},{1,0,0,0,0,0,0,0},{1,1,1,1,1,1,1,1}},
 {{1,1,1},{1,0,0},{1,1,1}},
 {{1,1,1,1,1,1,1,1,1,1},{1,0,0,0,0,0,0,0,0,0},{1,0,1,1,1,1,1,1,1,1},{1,0,1,0,0,0,0,0,0,1},{1,0,1,0,1,1,1,1,0,1},{1,0,1,0,0,0,1,1,0,1},{1,0,1,1,1,1,1,1,0,1},{1,0,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}},
 {{1,1,1,1,1},{1,0,1,0,1},{1,1,1,1,1}},
 {{1,1,1,1,1},{1,0,0,0,0},{1,0,1,1,1},{1,0,1,0,1},{1,1,1,1,1}},
 {{1,1,1,1},{1,1,0,1},{1,0,1,1},{1,1,1,1}}}

Альтернативное решение, 59 байт

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

Max@*MorphologicalComponents@*DeleteBorderComponents@*Image

Принимает тот же формат ввода, что и выше, но с ролями 0 s и 1s поменялись местами.

Причина, по которой мне нужно преобразовать это в Imageпервое, заключается в том, что в противном случае Mathematica рассмотрела бы все1 -элементы как часть одного компонента (потому что обрабатывает матрицу как матрицу меток компонента). Следовательно, если какой-либо 1элемент граничит с полем, он удалит их все. Когда DeleteBorderComponentsвместо этого используется образ, он выполняет неявную проверку подключения, чтобы найти компоненты.

В качестве альтернативы я мог бы вызвать MorphologicalComponents первым , что превратило бы ввод в подходящую матрицу меток, но если я сделаю DeleteBorderComponentsвторое, то больше не гарантируется, что максимальная метка компонента соответствует количеству компонентов (потому что я мог бы удалить меньший компонент).

Perl 5 , 154 байта

152 байта кода + 2 байта для -p0флага.

s/^ | $/A/gm;s/^.*\K | (?=.*$)/A/&&redo;/.*/;$@="@+"-1;for$%(A,X){$~="(.?.?.{$@})?";(s/$%$~ /$%$1$%/s||s/ $~$%/$%$1$%/s)&&redo}s/ /X/&&++$\&&redo}{$\|=0

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

Я думаю, что код довольно понятен.

Если вам нужны некоторые объяснения, чтобы понять, вот несколько шагов преобразований, сделанных программой на простой ввод (исходя из отсюда ), а затем некоторые пояснения ниже:

######
#     
# ####
# # #
#### #
######

######
# A
# ####
# # #
#### #
######

######
#AAAAA
#A ####
# A # #
#### #
######

######
#AAAAA
#A ####
# A # X #
#### #
######

######
#AAAAA
#A ####
# A # XX #
####ИКС#
######

Сначала s/^ | $/A/gm;s/^.*\K | (?=.*$)/A/&&redoзаменим пробелы на границе (1-е регулярное выражение для левого / правого, 2-е для нижнего / верхнего) на A(я выбираю этот символ совершенно произвольно).
Затем мы получаем ширину формы с /.*/;$@="@+"-1;.
Теперь мы хотим заменить каждое пространство, которое связано с a, Aна A(потому что, если пространство связано с a A, это означает, что оно не может быть частью дыры. Это сделано for$%(A,X){(s/$%(.?.?.{$@})? /$%$1$%/s||s/ (.?.?.{$@})?$%/$%$1$%/s)&&redo}. (Вы заметите, что это сделано один раз для As и один для Xs - объяснения для Xниже приведены.) Здесь есть два регулярных выражения: s/$%(.?.?.{$@})? /$%$1$%/sимеет дело с пробелами, которые находятся справа или снизу от А. AИ s/ (.?.?.{$@})?$%/$%$1$%/sс пробелами сверху или слева отA .
На данный момент единственные пробелы, которые остаются в строке, являются частью отверстий.
Пока еще есть пробелы, мы повторяем:
- Чтобы узнать, сколько там дырок, мы заменяем пробел на X( s/ /X/) и увеличиваем счетчик дырок ( $\++), и переделываем всю программу (на самом деле, мы хотим только повторить forцикл , но это меньше байтов, чтобы переделать всю программу).
- Затем forцикл заменит все пробелы, которые связаны с, на Xa X, так как они являются частью одного и того же отверстия.
В конце, $\|=0гарантирует, что если нет отверстий, 0вместо пустой строки печатается a. И $\неявно печатается благодаря -pфлажку.

Python 2, 282 байта

+100 для обработки диагональных касаний TT_TT (нам это действительно нужно?)
-119 благодаря руководству @Rod :)

Попробуйте онлайн . Принимает массив массивов символов «#» и пробелов в качестве входных данных.

A=input()
c=0
X=len(A[0])-1
Y=len(A)-1
def C(T):
 x,y=T
 global g
 if A[y][x]<'#':
    if y<1or y==Y or x<1or x==X:g=0
    A[y][x]='#';map(C,zip([x]*3+[min(x+1,X)]*3+[max(x-1,0)]*3,[y,min(y+1,Y),max(y-1,0)]*3))
while' 'in sum(A,[]):i=sum(A,[]).index(' ');g=1;C((i%-~X,i/-~X));c+=g
print c

Ищет первый пробел и помечает его как непустое ('#'). Рекурсивно проверяйте все окружающее, заполняя все пустые ячейки. Если какая-либо пустая ячейка текущей «дыры» окажется на счетчике границы, она не изменится, в противном случае она будет увеличена на 1. Повторяйте процесс до тех пор, пока не останется больше пробелов.

Python 2, 233 225 222 байта

math_junkie : -8 байт

Принимает 2d массив логических / целых чисел (0/1) в качестве входных данных

s=input()
o=[-1,0,1]
m=lambda x,y:0if x in[-1,len(s[0])]or y in[-1,len(s)]else 1if s[y][x]else(s[y].__setitem__(x,1),all([m(x+a,y+b)for a in o for b in o]))[1]
e=enumerate
print sum(m(x,y)-c for y,l in e(s)for x,c in e(l))

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

Отформатированная версия:

s = input()
o = [-1, 0, 1]
m = lambda x,y:
    0 if x in [-1, len(s[0])] or y in [-1, len(s)]
      else
        1 if s[y][x]
          else
            (s[y].__setitem__(x, 1),
             all([m(x + a, y + b) for a in o for b in o]))[1]
e = enumerate
print sum(m(x, y) - c for y, l in e(s) for x, c in e(l))

C # 7, 364 байта

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

using C=System.Console;class P{static void Main(){string D="",L;int W=0,H=0,z;for(;(L=C.ReadLine())!=null;H+=W=L.Length)D+=L;int[]S=new int[H*9];int Q(int p)=>S[p]<p?Q(S[p]):p;void R(int r)=>S[Q(r+=z)]=S[r]>0?z:0;for(z=H;z-->0;)if(D[z]<33){S[z]=z;R(1);R(W);R(W+1);R(W-1);}for(;++z<H;)S[Q(z)]*=z>H-W-2|z%W<1|z%W>W-2?0:1;for(;W<H;)z+=Q(W)<W++?0:1;C.WriteLine(z-H);}}

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

Завершить программу, принимает вход для стандартного входа, выход для стандартного выхода. Использует непересекающиеся наборы, чтобы определить временные дыры, и когда убивает любое прикосновение к границам (с некоторой хитростью для верхнего края).

Отформатированный и закомментированный код:

using C=System.Console;

class P
{
    static void Main()
    {
        string D="", // the whole map
            L; // initally each line of the map, later each line of output

        // TODO: some of thse might be charable
        int W=0, // width, later position
            H=0, // length (width * height)
            z; // position, later counter

        // read map and width
        for(;(L=C.ReadLine())!=null; // read a line, while we can
                H+=W=L.Length) // record the width, and increment height
            D+=L; // add the line to the map

        // disjoint sets
        int[]S=new int[H*9]; // generousness (relieve some bounds checking)
        // note that S[x] <= x, because we call R with decending values of z

        // returns whatever p points to
        int Q(int p)=>S[p]<p?Q(S[p]):p;
        // points whatever r points to at z if r is empty
        void R(int r)=>S[Q(r+=z)]=S[r]>0?z:0; // note that is never called when z=0

        // fill out disjoint sets
        for(z=H;z-->0;)
            if(D[z]<33) // if cell is empty
            {
                S[z]=z; // point it at itself

                // point the things next  to z at z
                R(1);
                R(W);
                R(W+1);
                R(W-1);
            }

        // zero sets which are against the left, bottom, or right edges
        for(;++z<H;)
            S[Q(z)]*=z>H-W-2|z%W<1|z%W>W-2?0:1; // TODO?: this suggests inverting the first loop (NOTE: would break S[x]<=x)

        // starting from the second row, count all the sets that point to this cell (ignores any non-zeros pointing to first row)
        for(;W<H;)
            z+=Q(W)<W++?0:1;

        C.WriteLine(z-H);
    }
}

Улитки , 48 байт

!{\ z`+~}\ {t\ z!.!~=((lu|u.+r)!(.,~},!{t\ z!.!~

Ungolfed:

!{
    (\   z)+
    ~
}
\ 
{
    t \ 
    z !.!~
    ={
        (lu|u.+r)
        !(.,~)
    }
},
!{
    t \ 
    z !.!~
}

JavaScript (ES6), 192 байта

v=a=>Math.min(...a=a.map(s=>s.length))==Math.max(...a);
f=(s,t=(u=` `.repeat(w=s.search`
`+1))+`
`+s.replace(/^|$/gm,` `)+`
`+u,v=t.replace(RegExp(`( |@)([^]{${w},${w+2}})?(?!\\1)[ @]`),`@$2@`))=>t!=v?f(s,v):/ /.test(t)?f(s,t.replace(` `,`@`))+1:-1

<textarea id=i rows=10 cols=10></textarea><input type=button value=Count onclick=o.textContent=/^[\s#]+$/.test(i.value)*v(i.value.split`\n`)?f(i.value):`Invalid_Entry`><span id=o>

Основываясь на моем ответе Обнаружить провальные замки» . Сначала строка дополняется пробелами, чтобы создать область вокруг фигуры. Затем RegExp ищет два соседних квадрата, один из которых содержит @, другой содержит пробел, и заменяет их оба на @. Если он не может этого сделать, он заполняет пробел знаком @и считается как новая дыра. Наконец один вычитается для учета окружающей области.