Отдельный прототип

Программа 4: ищем сам разрез

Два режима: простая линия от границы до границы и полная граница между частями, которая может быть замкнутой или состоять из нескольких компонент.

Ищутся простые пути по рёбрам сетки, соединяющие две точки внешней границы фигуры.
Ограничения варианта А: до 30 клеток; до 250 000 продолжений пути; первые 100 разрезов.
исходная фигура часть A часть B линия разреза
Математические подробности

Вариант А. Перебираются простые пути в графе рёбер клетчатой сетки. После достижения другой точки внешней границы путь проверяется и дальше не продолжается. Успешный путь обязан точно совпадать с общей границей двух получившихся частей.

Вариант Б. Ищутся связные половины фиксированной площади, содержащие выбранную стартовую клетку. Для каждой подходящей пары частей вычисляется вся их общая граница. Поэтому находятся также замкнутые и многокомпонентные границы.

Вариант Б полный для разбиений на две связные равные части в пределах установленного перебора. Если разрешать несвязные части, потребуется отдельный режим.