Задача о прямоугольниках (чисто алгоритмическая)

Когда ночью не спится, включаю телик. Как-то раз напоролся на игру "деньги на проводе" по ТНТ. Вот и возникла идея решить одну из предложенных там задач в общем случае.

Задача такая. Дан прямоугольник (n строк, m столбцов), "разлинованный" на клетки (как тетрадь в клетку). Но некоторые "границы" между клетками отсутствуют. Нужно подсчитать количество прямоугольников, образуемых этой системой клеток. Думаю, не нужно объяснять, что в данном случае считать прямоугольником: прямоугольником является любая система клеток, ограничиваемая двумя вертикальными и двумя горизонтальными линиями, при этом, естественно, линии не должны проходить по непрочерченным "стенкам".
В приведенном ниже примере пять прямоугольников:
____
|_|_|
|___|
- левая верхняя клетка;
- правая верхняя клетка;
- прямоугольник, образованный двумя верхними клетками;
- нижний прямоугольник;
- вся система тоже является прямоугольником.

Мой вариант решения использует комбинаторику. Обозначения: n - размер генерального прямоугольника в ширину, m - размер генерального прямоугольника в длину, k - количество "непрочерченных" стенок. Абсциссы и ординаты как клеток, так и стенок нумеруются по математическим правилам - от единицы.

Прямоугольник однозначно идентифицируется парой противоположных углов - скажем, левым верхним и правым нижним. Поэтому мы можем подсчитать число прямоугольников, которые мы могли бы образовать, если бы все стенки между клетками существовали, были "прочерчены".
Очевидно, абсциссу левого верхнего угла мы можем выбрать n способами. Причем для каждой выбранной абсциссы левого верхнего угла абсцисса правого нижнего выбирается n+1-i способами, где i - абсцисса текущего левого верхнего угла. Соответственно, число способов образовать абсциссу левого верхнего угла и абсциссу правого нижнего угла равно:
Сумма от i=1 по n (n+1-i) = сумма от i=1 по n (i) = n * (n+1) / 2.
Независимо от выбора абсциссы, ординаты мы можем выбрать
m (m+1) / 2 способами. Благодаря независимости выбора абсциссы и ординаты, получаем общее количество способов (обозначим через S0):
S0 = n * (n+1) / 2 * m * (m+1) / 2.
Теперь для каждой непрочерченной стенки (в нашем примере такая стенка одна) число прямоугольников, которое нельзя провести через данную стенку. Сумму этих чисел обозначим S1.
Используя метод включения и исключения, возьмем полученное число S0 и вычтем из него число прямоугольников, которое нельзя провести через каждую отдельно взятую стенку, т. е. S1. Но при этом мы дважды вычли прямоугольники, которые нельзя провести одновременно через две стенки, поэтому подсчитаем их количество и прибавим их, и т. д.:

S = S0 + S1 - S2 + S3 - ... (+-) Sk

"Непрочерченную стенку" можно идентифицировать координатой клетки, для которой эта стенка является левой (если стенка вертикальная) или верхней (если горизонтальная). Если же стенка находится в самом низу генерального прямоугольника, ей не соответствует ни одна клетка; присвоим ей ординату m+1; если она находится на правой "стене" генерального прямоугольника, т. е. опять же вне зоны клеток, присвоим ей абсциссу n+1. Таким образом, абсцисса стенки меняется от 1 до n+1, ордината от 1 до m+1.

Тогда число S1 (число прямоугольников, проходящих через каждую "непрочерченную" стенку, просуммировано по всем таким стенкам) можно посчитать по нижеследующим формулам.

1. Если стенка горизонтальная, через нее нельзя провести i * (n+1-i) * m прямоугольников.
2. Если стенка вертикальная, через нее нельзя провести j * (m+1-j) * n прямоугольников.
Здесь (i, j) - соответственно абсцисса и ордината стенки. Отмечу, что для горизонтальной стенки число не зависит от ее ординаты, а для вертикальной - от абсциссы.
Очевидно, для подсчета S1 требуется время порядка O(k), где k - количество непрочерченных стенок.

Теперь нужно сосчитать число S2 (число прямоугольников, проходящих через пару "непрочерченных" стенок, просуммировано по всевозможным парам стенок).

1. Для пары горизонтальных стенок (i1, j1); (i2, j2):
1а. Если их ординаты не равны (j1 <> j2), т. е. стенки лежат на противоположных стенках прямоугольника, имеем формулу i1 * (n+1-i2)
(предполагается, что i1 <= i2, в противном случае просто переобозначим их).
1б. Если их ординаты равны (j1 = j2), т. е. стенки лежат на одной стороне прямоугольника, имеем формулу i1 * (n+1-i2) * m (опять же предполагается i1 <= i2).
2. Для пары вертикальных стенок формулы идентичны.
3. Для пары "горизонтальная-вертикальная" (обозначим через (i1, j1) горизонтальную, (i2, j2) вертикальную):
3а. Если i1 < i2 и j2 < j1: i1*j2
3б. Если i1 < i2 и j2 >= j1: i1 * (m+1-j2)
3в. Если i1 >= i2 и j2 < j1: (n+1-i1) * j2
3г. Если i1 >= i2 и j2 >= j1: (n+1-i1) * (m+1-j2)
Число всевозможных пар стенок равно C (2, k) = k! / (2! * (k-2)!) = k * (k-1) / 2, т. е. для подсчета S2 требуется время порядка O (k^2), где k - количество стенок.

Формулы для S3 и т. д. я приводить не буду, поскольку это займет много места. Однако добавлю, что можно вывести формулы и для S4; а дальнейшие случаи сводятся к S1-S4 (поскольку прямоугольник имеет только 4 стороны).

Итак, выводы. Для подсчета числа прямоугольников используется метод включения и исключения, для чего нам нужно провести 1 вычисление для подсчета S0, k вычислений для подсчета S1, k (k-1) / 2 вычислений для подсчета S2 и т. д. Получим общее число вычислений:
Сумма от i=0 по k C(i,k) = 2^k.
Таким образом, алгоритмическая сложность такого решения O (2^k).
Тут есть возможность для оптимизации. Если при вычислении какого-то из чисел Si мы получили ноль, дальнейшие числа вычислять не имеет смысла - они также будут нулевыми (если ни один прямоугольник не проходит, скажем, через произвольную тройку стенок, то ни один прямоугольник не будет также проходить и через четверку стенок). Поэтому в этот момент имеет смысл прервать вычисления и выдать результат. Однако оценку сложности такого оптимизированного алгоритма провести сложно, поскольку нельзя даже сказать определённо, с какой вероятностью алгоритм прервется на каком-то определенном шаге, поэтому будем считать, что сложность алгоритма не хуже O (2^k).
Отмечу, что если решать задачу "напролом", простым перебором вариантов, сложность задачи составит O (2^(n*m)). Однако, если учесть, что для каждого варианта прямоугольника нужно выполнять поиск стенок, через которые он может проходить, и предположить, что время поиска логарифмическое, получим несколько худшее время: O (2^(n*m) * log2 k).

Внимание, вопрос :) Есть ли более быстрый алгоритм?