Abstraction,

Да, ляпнул недодумавши... Критерий нужен для границ, а не углов. И чтобы получить его, надо два прохода по матрице... Надо будет сравнить с количеством итераций при втором подходе (с построением списка)

Usman,

Суть алгоритма понятна, но пропускаете варианты... Ну и главный вопрос-то (что для варианта schwa, что для вашего) - как выявить именно нужный "пригодный" вариант при анализе разрезов.

rockclimberschwa написал на предыдущей странице...
Сложности алгоритма, по крайней мере, зависит от К, а не от M х N.В указанном виде - от K зависит количество итераций для разбиения (в худшем случае - на каждой итерации список возрастает на 6 элементов), а от NxM зависит как раз анализ "пригодности". Так что сложность алгоритма - надо посмотреть...

rockclimber,

Ну да, алгоритм ТС не пойдёт. А вот алгоритм с последовательным добавлением "непригодных" секторов попробую попозже изобразить... Там действительно получается похоже на ДП:
- исходное положение: список из одного "пригодного" элемента (NxM) (это нулевое положение [K-1]).
- считая, что для [K-1] элементов - список "пригоден", добавляем [K]-элемент: проходим список, находим элементы, куда попадает "непригодный", заменяем эти элементы на 2/3/4 новых элемента, и так далее.
- составленный список надо проанализировать, и выбросить те элементы, которые полностью покрываются каким-либо другим элементом .
Я вот интуитивно понимаю, что результат будет около дела, но надо это доказать... Инвариантность порядка добавления "непригодных, невозможность существования "составных" ответов (прямоугольник, сложенный из неполностью пересекающихся элементов списка); плюс неплохо бы оптимизировать последовательность действий - например, анализ попарного пересечения-покрытия элементов проводить в момент добавления в список. Тогда можно вплотную приблизиться к сложности O(K*lnK).