Вопрос № 1078600 - Информатика

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

Чтобы огородить такую группу из 9 деревьев, нужно 20 блоков:

Требуется написать программу, которая по заданной конфигурации рощи определит минимально необходимое число блоков для забора.
Формат входных данных
В первой строке файла Zabor.in записано одно число N – количество строк данных. В следующих N строках содержатся последовательности из K символов (единиц или нулей). Единицей обозначается расположение реликтового дерева, а нулем – его отсутствие в узле координатной сетки.

Формат выходных данных
В файле Zabor.out выводится число блоков забора, необходимое для огораживания.

Составьте программу и просчитайте для трех тестовых файлов Zabor.in. (данные доступны для копирования в буфер обмена)
1) Zabor.in
10
1111111101
1000000101
1011110101
1010010101
1010010101
1011010101
1010000101
1011111101
1000000001
1111111111

2) Zabor.in
6
001111111111110
011100010000011
010001111101101
110011000111001
010000111101111
011111100111000

3) Zabor.in
8
1111111111111111111111111
0100000000001000000000001
1111010101001000000000001
0000011111111111111111001
0000010000001000000000001
0010010001111111100000001
0111110001000000100000001
0010000001111011111111111

В ответе запишите результаты тестов через запятую, без пробелов.

Пример входных, выходных данных и вывода ответа.
1) Zabor.in
3
001110
011011
011110

2) Zabor.in
4
0000000000
0000000000
0000000000
0000000000

3) Zabor.in
4
0000000000
0000000000
0000000000
0000000000

Zabor.out

1) 16     2) 0    3) 32

Запись ответа: 16,0,32