Answer
t.me/js_testОтвет:
const minArea = (image, x, y) => { let minX = Number.MAX_SAFE_INTEGER; let minY = Number.MAX_SAFE_INTEGER; let maxX = Number.MIN_SAFE_INTEGER; let maxY = Number.MIN_SAFE_INTEGER; const rows = image.length; const cols = image[0].length; const DFS = (image, x, y) => { if (x < 0 || x >= rows || y < 0 || y >= cols || image[x][y] != '1') return; image[x][y] = '0'; minX = Math.min(minX, x); minY = Math.min(minY, y); maxX = Math.max(maxX, x); maxY = Math.max(maxY, y); DFS(image, x + 1, y); DFS(image, x - 1, y); DFS(image, x, y + 1); DFS(image, x, y - 1); }; DFS(image, x, y); return (maxX - minX + 1) * (maxY - minY + 1); };
Обьяснение:
Классический подход в подобных задачах — использование поиска в глубину (Depth-first search, DFS).
То есть из каждой текущего пикселя матрицы мы запускаем поиск вглубь матрицы до тех пор, пока встречаются поврежденные пиксели. И для каждой из сторон мы сохраним крайние координаты поврежденных пикселей. Таким образом, мы сможем определить длину поврежденной области по оси X и оси Y, и найдем площадь поврежденной области.
Детали реализации:
- Eсли исходная задача позволяет изменять исходные данные, в нашем случае, это матрица, то для того, чтобы алгоритм не считал уже пройденные элементы, мы можем изменить значение поврежденного пикселя.
- Если вы не хотите изменять исходные данные, то обычно используется вспомогательный массив посещенных координат visited. Таким образом на каждом шаге поиска в глубину, вы пропускаете уже пройденные элементы.
В нашем случае, мы можем изменить исходные данные, поэтому для простоты воспользуемся 1м вариантом.
Код для проверки:
const minArea = (image, x, y) => { let minX = Number.MAX_SAFE_INTEGER; let minY = Number.MAX_SAFE_INTEGER; let maxX = Number.MIN_SAFE_INTEGER; let maxY = Number.MIN_SAFE_INTEGER; const rows = image.length; const cols = image[0].length; const DFS = (image, x, y) => { if (x < 0 || x >= rows || y < 0 || y >= cols || image[x][y] != '1') return; image[x][y] = '0'; minX = Math.min(minX, x); minY = Math.min(minY, y); maxX = Math.max(maxX, x); maxY = Math.max(maxY, y); DFS(image, x + 1, y); DFS(image, x - 1, y); DFS(image, x, y + 1); DFS(image, x, y - 1); }; DFS(image, x, y); return (maxX - minX + 1) * (maxY - minY + 1); }; const pixels = [ ['0', '0', '1', '0'], ['0', '1', '1', '0'], ['0', '1', '0', '0'], ]; console.log(minArea(pixels, 0, 2));