Здравствуйте, Philip_PV, Вы писали:

P_P>2. Контрольная работа

Казалось бы...
Любой вырезанный прямоугольник можно задать парой проекций — [x1,x2], [y1,y2], 0<=x1<x2<=N, 0<=y1<y2<=M (где целым координатам соответствуют линии сетки).
Верхняя граница количества разных прямоугольников, очевидно, U = Ux*Uy = C(N,2)*C(M,2) = N*(N-1)*M*(M-1)/4.

Основной приём подсчёта:
Возьмём произвольный отрезок [x1,x2]. Он вырезает из листа колонку, в которой встречается некоторое количество закрашенных клеток.
Будем резать эту колонку на горизонтальные полоски [y1,y2], так, чтобы они были чистыми.

Перебор всех Ux вариантов — чересчур дорогое удовольствие. Однако, заметим, что если колонки [x0,x1], [x2,x3] чисты, то [x0,x3] будет содержать столько же чистых горизонтальных полосок, сколько и [x1,x2]. Поэтому, найдя количество горизонтальных полосок S(x1,x2), мы найдём ответ для значений S(x0..x1,x2..x3), итого (x1-x0+1)*(x3-x2+1).

Таким образом, первая оптимизация состоит в том, чтобы найти проекции закрашенных клеток на ось X — и далее перебирать уже по ним.

Далее: пусть закрашенные клетки упорядочены по возрастанию y в пределах каждого подмножества с равными x.
Результат слияния нескольких таких массивов (для x1..x2) даст множество проекций закрашенных клеток в колонке [x1,x2]. После чего подсчёт количества полосок не составляет труда: каждый чистый отрезок [y1,y2] даёт C(y2-y1,2) разных непустых подотрезков.

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

Битовая карта удобна ещё и тем, что её можно многократно переиспользовать.
Это M-мерный вектор-столбец неотрицательных чисел (не нули — закрашенные).
Каждой единичной колонке соответствует M-мерный вектор-столбец чисел {0,1} (1 — закрашено).
Пусть у нас есть n закрашенных столбцов X[1], ..., X[n].
Битовая карта B изначально заполнена нулями.
Полоска x1 : B = X[1]. Посчитали число полосок S, расширили на пробельные колонки слева-справа, т.е. S*(x1-0+1)*(x2-x1+1).
Полоска x2 : B += X[2]. Снова посчитали, умножили на (x1-0+1)*(x3-x2+1).
...
Полоска xn : B += X[n].
Теперь начнём движение назад. Исключим колонку x1 (для которой мы уже перебрали все сочетания).
x2..xn : B -= X[1].
x2..xn_1 : B -= X[n].
x2..xn_2 : B -= X[n-1].
...
x2 : B -= X[3].

x3 : B = X[3].
x3..x4 : B += X[4].

И так далее.

Естественно, что векторы X[] заданы номерами ненулевых элементов. Поэтому инкремент-декремент B сводится к пробеганию соответствующего массива номеров и инкременту/декременту ячеек по этим номерам.
Можно подумать над тем, как более эффективно (чем сканированием M элементов) искать пустые отрезки в B.