Посмотрим на самую левую, самую верхнюю, самую нижнею и самую правую башни. Заметим, что они точно лежат в покрытой области и являются самыми крайними точками покрытой области. Теперь построим границу нужной области, которая находится между самой левой и самой верней клеткой. Отсортируем все клетки по x. Тогда если мы сначала встретили точку (x1, y1), а потом точку (x2, y2) где y2 > y1, то мы добавляем в нашу границу два отрезка [(x1, y1), (x2, y1)] и [(x2, y1), (x2, y2)]. После чего мы повторяем тоже самое для всех остальных частей границы нужной области. В конце не забываем закрасить область внутри.
Крайним случаем является ситуация, где все башни лежат на одной диагонали. И представленный алгоритм на нем найдет не минимальное по площади покрытие. Поэтому этот случай нужно рассмотреть отдельно.