Блог Ромки

Задача 2. “Прямоугольники”

На квадратном листе бумаги размера N*N нарисовано несколько прямоугольников, какждый прямоугольник состоит из клеток, различные прямоугольники не накладываются друг на друга, и не соприкасаются. Дана целочисленная квадратная матрица N*N, в которой элемент равен 0 если он не принадлежит прямоугольнику, и отличенот 0 в противном случае. Определите число прямоугольников.

Формат входных данных:

В первой строке указывается размерность массива. Далее идет сам массив в котором “#” обозначают прямоугольники, а “0” остальные клетки.

Формат выходных данных:

Число прямоугольников.

Пример файла входных данных:
12
0 0 0 0 0 0 0 0 0 0 0 0
0 # # 0 # # # 0 0 # # #
0 # # 0 # # # 0 0 # # #
0 # # 0 # # # 0 0 # # #
0 # # 0 # # # 0 0 # # #
0 # # 0 0 0 0 0 0 # # #
0 0 0 0 0 0 0 0 0 # # #
0 # # # 0 # # # 0 0 0 0
0 # # # 0 # # # 0 # # 0
0 # # # 0 0 0 0 0 # # 0
0 0 0 0 0 0 0 0 0 # # 0
0 0 0 0 0 0 0 0 0 0 0 0

Пример выхода:
6

За задачу давали 50 очков поэтому я решал её первой. Алгоритм достаточно банален но много писанины в коде:
Бежим по матрице слева направо, сверху вниз. Находим первое препятсвие. Увеличиваем счетчик прямоугольников. Зануляем прямоугольник. Проверяем не вся ли матрица в 0, если нет то продолжаем сначала.

Все написал, но когда уже ушел вспомнил, что можно было бежать не сначала каждый раз, а стого места где остановился. Конечно когда матрица маленькая это не страшно, но если их делать по мегабайту то это может иметь нехорошие последствия. Но самое смешное, что я забыл вызвать free() в самом конце Т_Т. Но задача решена на 100% если не считать недочетов.