Задача: 835. Image Overlap
Сложность: medium

Вам даны два изображения, img1 и img2, представленные как бинарные квадратные матрицы размером n x n. Бинарная матрица содержит только 0 и 1 в качестве значений.
Мы можем сдвигать одно изображение как угодно, перемещая все биты 1 влево, вправо, вверх и/или вниз на любое количество единиц. Затем мы помещаем его поверх другого изображения. После этого мы можем вычислить перекрытие, подсчитав количество позиций, на которых в обоих изображениях есть 1.

Также обратите внимание, что при сдвиге не допускается никакое вращение. Любые биты 1, которые перемещаются за пределы границ матрицы, стираются.

Верните максимальное возможное перекрытие.

Пример:

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.

👨‍💻 Алгоритм:

1⃣Определите функцию shiftAndCount(xShift, yShift, M, R), которая смещает матрицу M относительно матрицы R на координаты (xShift, yShift) и подсчитывает количество единиц в зоне перекрытия.

2⃣Организуйте цикл по всем возможным комбинациям координат смещения (xShift, yShift).

3⃣На каждой итерации вызывайте функцию shiftAndCount() дважды для обоих направлений смещения и обновляйте максимальное количество перекрытий.

😎 Решение:

class Solution {
    function shiftAndCount($xShift, $yShift, $M, $R) {
        $leftShiftCount = 0;
        $rightShiftCount = 0;
        $rRow = 0;
        for ($mRow = $yShift; $mRow < count($M); ++$mRow) {
            $rCol = 0;
            for ($mCol = $xShift; $mCol < count($M); ++$mCol) {
                if ($M[$mRow][$mCol] == 1 && $M[$mRow][$mCol] == $R[$rRow][$rCol]) {
                    $leftShiftCount++;
                }
                if ($M[$mRow][$rCol] == 1 && $M[$mRow][$rCol] == $R[$rRow][$mCol]) {
                    $rightShiftCount++;
                }
                $rCol++;
            }
            $rRow++;
        }
        return max($leftShiftCount, $rightShiftCount);
    }

    function largestOverlap($A, $B) {
        $maxOverlaps = 0;
        for ($yShift = 0; $yShift < count($A); ++$yShift) {
            for ($xShift = 0; $xShift < count($A); ++$xShift) {
                $maxOverlaps = max($maxOverlaps, $this->shiftAndCount($xShift, $yShift, $A, $B));
                $maxOverlaps = max($maxOverlaps, $this->shiftAndCount($xShift, $yShift, $B, $A));
            }
        }
        return $maxOverlaps;
    }
}

Ставь 👍 и забирай 📚 Базу знаний