Помагите

← →
nika_ufc (2002-10-06 14:23) [0]

задача такая: дана матрица, заполнена ноликами и единицами. моя программа должна найти и напечатать сколько прямоугольников в матрицею пример
10000
10011
00011
00000
11100
ответ: прямоугольников=3
такой вариант не обсуждается:
1 1000
10011
00011
00000
11100

← →
nika_ufc (2002-10-06 14:27) [1]

И ешо
прямоугольники не должни пересекать друг-друга.

← →
Arcus (2002-10-07 18:02) [2]

Т.е. размер минимального прямоугольника 2х2?
Берем элемент (i, j). Сканируем i-ю строку начиная с j-ого столбца. Пусть насчитали к одинаковых элементов. Берем i + 1 строку, сканируем до j + k элемента или до первого отличного элемента (что вперед наступит) и т.д. до i + m строки. Получаем прямоугольник (i, j) - (i + m, j + k). Проверяем, что это прямоугольник.
Чтоб не пересекались, заводишь булевскую матрицу по размеру исходной. Сначала все элементы false. Находишь прямоугольник - перекидываешь соответствующие элементы в true. Сканирование начинаешь с проверки соответствующего элемента булевской матрицы - если он true, то все, дальше можно не ходить.

Помагите Найти похожие ветки