Answer

Ответ:

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));