Сложность: 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() дважды для обоих направлений смещения и обновляйте максимальное количество перекрытий.
😎 Решение:
public class Solution {
public int ShiftAndCount(int xShift, int yShift, int[][] M, int[][] R) {
int leftShiftCount = 0, rightShiftCount = 0;
int rRow = 0;
for (int mRow = yShift; mRow < M.Length; ++mRow) {
int rCol = 0;
for (int mCol = xShift; mCol < M.Length; ++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 Math.Max(leftShiftCount, rightShiftCount);
}
public int LargestOverlap(int[][] A, int[][] B) {
int maxOverlaps = 0;
for (int yShift = 0; yShift < A.Length; ++yShift) {
for (int xShift = 0; xShift < A.Length; ++xShift) {
maxOverlaps = Math.Max(maxOverlaps, ShiftAndCount(xShift, yShift, A, B));
maxOverlaps = Math.Max(maxOverlaps, ShiftAndCount(xShift, yShift, B, A));
}
}
return maxOverlaps;
}
}Ставь 👍 и забирай 📚 Базу знаний