Списки управления доступом (Access Control List – ACL) используются для управления маршрутизацией пакетов между множеством источников и приемников. ACL представляет собой прямоугольную матрицу, строки которой соответствуют источникам сигнала, а столбцы – приемникам. Если передача пакета между источником и приемником разрешена, то в соответствующей ячейке ставится «1», в ином случае ставится «0» и попытка передачи пакета между данным источником и приемником будет проигнорирована.

Для минимизации памяти при хранении ACL используются списки прямоугольных правил (Rectangular Rules List –RRL). Каждое правило при помощи четырех координат описывает прямоугольную подматрицу ACL-матрицы, внутри которой содержатся одинаковые значения (например, только единицы или только нули). Таким образом, одно правило охватывает область исходной матрицы и хранит ее при помощи четырех чисел.

Пусть имеется некоторая матрица ACL, описывающая процесс маршрутизации между множеством источников и приемников.



Задача

Ваша задача – преобразовать исходную ACL матрицу в как можно меньшее количество прямоугольных правил (разбить исходную матрицу на как можно меньшее количество подматриц, состоящих только из нулей или только из единиц).