Найти количество прямоугольников в двумерном байтовом массиве

12 
0000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000011111100000000000000000000011111111111111100000000000000000
0000000000011111100000000000000000000011111111111111100000000000000000
0000000000011111100000000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000000111111000000000000000000011111111111111100000000000000000
0000000000000100001000000111111000000011111111111111100000000010000000
0000000000000100001000000111111000000000000000000000011000000000000000
0000000000000111111000000111111000000000000000000000011000000000000000
0000000000000000000000000000111111000000000000000000000000000000000000
0000000000000000000000000000111111000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000

Вам дан двумерный массив байтов размером mx n. Гарантируется, что все байты равны 1 или 0. Найдите количество прямоугольников, представленных 1, при просмотре в 2d, как показано выше.

Для подсчета учитываются только полностью заполненные прямоугольники.
Прямоугольники должны быть окружены нулями, если они не находятся на краю (хотя прямоугольники, соприкасающиеся с диагональю 1, вполне допустимы (см. Пример.)).

Например, в приведенном выше массиве есть 5 правильных прямоугольников.

Вы можете использовать любой язык.

popularity-contest микробный
источник
1
Я думаю, что лучший способ сказать это - сказать, что: прямоугольники должны быть окружены
нулями
Выполнено. Спасибо за формулировку на лучшем английском.
микробиан
Как насчет 1100\n1100\n0011\n0011?
Cruncher
1
Я думаю, именно поэтому я написал «смежные / перекрывающиеся». Это 2 правильных прямоугольника из моего первоначального намерения. Но «окружающее» условие ограничивает их сейчас. У вас есть лучший способ объяснить это
микробиан
1
Даже в смежных условиях неоднозначно, означает ли диагональ соседние или нет. Та же самая двусмысленность, окруженные ли средства или нет, окруженные в углах, или только стороны
Cruncher

Ответы:

2

GolfScript, 107 символов

.n?):L;'1'/{,}%{1$+)}*;][]\{:A{{+}+[1L.~)-1]%&}+1$\,.@^\[[[A]]+{|}*]+}/{.{L%}{%$..&1$,1$,/*$=}:C~\{L/}C&},,

Ввод должен быть дан на STDIN.

Примеры:

11
01
-
0

111
111
-
1

100
001
001
-
2

11100
10101
11100
-
1

101
010
101
-
5
Говард
источник
См. Комментарии выше - кажется, что «действительные» прямоугольники должны иметь ширину / высоту как> 1.
Пол Р
@PaulR Это правило не написано в вопросе, по всем разумным определениям, это совершенно мелкие прямоугольники - возможно, я добавлю это позже.
Говард
Я согласен с вашим определением - я просто отметил несоответствие в комментариях - похоже, что ОП необходимо обновить вопрос, чтобы сделать его более определенным.
Paul R
Я уточнил, что прямоугольник размера 1 действителен.
микробиан
Но вы также сказали в комментариях в ответ: «Только для пояснения, вырожденные прямоугольники не должны быть подсчитаны, верно? Например, недействительны единичная 1 или одна подстрока / подколонка смежной 1?» говоря: «Да, они недействительны, и не должны учитываться».
Paul R