Damaged pixels
Задача: Находим блок поврежденных пикселей. Вам дана матрица пикселей, где ‘0’ представляет рабочий пиксель, а ‘1’ представляет поврежденный пиксель.
- Поврежденные пиксели связаны (т.е. есть только одна поврежденная область на матрице). Пиксели соединены по горизонтали и вертикали.
- Также вам даны два целых числа x и y, которые представляют расположение одного из поврежденных пикселей.
Необходимо найти площадь наименьшего (выровненного по оси) прямоугольника, охватывающего все поврежденные пиксели.
Входные данные: Стороны матрицы имеют размер от 1 до 100 пикселей включительно. Элементы матрицы символы ‘0’, ‘1’.
Вывод: площадь наименьшего прямоугольника, охватывающего все поврежденные пиксели.
Пример:
matrix = [
[‘0’,’0',’1',’0'],
[‘0’,’1',’1',’0'],
[‘0’,’1',’0',’0']
].
x = 0, y = 2
Output: 6
Разбор
Классический подход в подобных задачах — использование поиска в глубину (Depth-first search, DFS).
То есть из каждой текущего пикселя матрицы мы запускаем поиск вглубь матрицы до тех пор, пока встречаются поврежденные пиксели. И для каждой из сторон мы сохраним крайние координаты поврежденных пикселей. Таким образом, мы сможем определить длину поврежденной области по оси X и оси Y, и найдем площадь поврежденной области.
Детали реализации:
- Eсли исходная задача позволяет изменять исходные данные, в нашем случае, это матрица, то для того, чтобы алгоритм не считал уже пройденные элементы, мы можем изменить значение поврежденного пикселя.
- Если вы не хотите изменять исходные данные, то обычно используется вспомогательный массив посещенных координат visited. Таким образом на каждом шаге поиска в глубину, вы пропускаете уже пройденные элементы.
В нашем случае, мы можем изменить исходные данные, поэтому для простоты воспользуемся 1м вариантом.
Реализация
