UniLecs #Task. Two squares
Задача: художник изобразил два черных квадрата с одинаковой стороной K на квадратном холсте размера N². Квадраты могут пересекаться, касаться и даже совпадать. В какой-то момент он забыл число K.
По заданному N и информации о цвете клеток холста, помогите художнику найти левые верхние углы каждого из квадратов и их длину K.
Входные данные:
- Число N (N <= 2000);
- Символьная матрица NxN, которая содержит следующие символы: “#” или “.”. Где “#” — черная клетка, а “.” — белая клетка (без кавычек).
Выходные данные:
- число K;
- Два числа x1 и y1 — левая верхняя точка первого квадрата;
- Два числа x2 и y2 — левая верхняя точка второго квадрата.
Пример 1:
N = 6
……
.###..
.#####
.#####
…###
……
Output:
K = 3; T1 = (x1: 2, y1: 2); T2 = (x2: 3, y2: 4).
Пример 2:
N = 6
……
….##
.##.##
.##…
……
……
Output: K = 2, T1 = (x1: 3, y1: 2); T2 = (x2: 2, y2: 5).
Разбор
Перебираем элементы матрицы по строчно, сохраним первый символ черной точки, это будет верхний левый угол 1го квадрата. Последний символ черной точки в матрице, ктр мы сохраним будет нижним правым углом 2го квадрата.
Дальше необходимо определить длину квадратов. Для этого будем одновременно двигаться вправо и вниз из 1й найденной точки, пока не наткнемся на белую точку или границу поля.
Сложность решения O(N²).
Реализация
https://gist.github.com/unilecs/fc17f1db3f0a680c87645e2945295ccd
