Сложность: 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 {
func shiftAndCount(_ xShift: Int, _ yShift: Int, _ M: [[Int]], _ R: [[Int]]) -> Int {
var leftShiftCount = 0, rightShiftCount = 0
var rRow = 0
for mRow in yShift..<M.count {
var rCol = 0
for mCol in xShift..<M.count {
if M[mRow][mCol] == 1 && M[mRow][mCol] == R[rRow][rCol] {
leftShiftCount += 1
}
if M[mRow][rCol] == 1 && M[mRow][rCol] == R[rRow][mCol] {
rightShiftCount += 1
}
rCol += 1
}
rRow += 1
}
return max(leftShiftCount, rightShiftCount)
}
func largestOverlap(_ A: [[Int]], _ B: [[Int]]) -> Int {
var maxOverlaps = 0
for yShift in 0..<A.count {
for xShift in 0..<A.count {
maxOverlaps = max(maxOverlaps, shiftAndCount(xShift, yShift, A, B))
maxOverlaps = max(maxOverlaps, shiftAndCount(xShift, yShift, B, A))
}
}
return maxOverlaps
}
}Ставь 👍 и забирай 📚 Базу знаний