| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [c++] Определить число прямоугольников |
| Автор: divinepro 30.5.2010, 11:32 |
| Помогите, пожалуйста, решить задачку на c++ На квадратном листе клетчатой бумаги размером n на n нарисовано несколько прямоугольников, каждый прямоугольник состоит из клеток, различные прямоугольники не накладываются друг на друга и не соприкасаются. Дана целочисленная квадратная матрица порядка n, в которой элемент равен 0, если соответствующая клетка принадлежит какому-либо прямоугольнику, и отличен от нуля в противном случае. Определить число прямоугольников |
| Автор: Sanaff 30.5.2010, 23:34 |
| Общий алгоритм можно так описать: Создали пустую матрицу такого же размера, заполнили нулями (для меток пройденных точек) Идём по матрице слева направо и сверху вниз. если встретили не 0, то это начало прямоугольника. идём вправо, пока 0 не встретим - это правая граница прямоугольника. и идём вниз, пока 0 не встретим - это нижняя граница прямоугольника. в матрице меток эту всю площадь прямоугольника заполняем единицами. счётик прямоугольников увеличиваем на 1. идём дальше, но если текущий элемент помечен в матрице меток как занятый ( = 1 ), то пропускаем его. |