# 835. Image Overlap

Two images A and B are given, represented as binary, square matrices of the same size.  (A binary matrix has only 0s and 1s as values.)

We translate one image however we choose (sliding it left, right, up, or down any number of units), and place it on top of the other image.  After, the  overlap  of this translation is the number of positions that have a 1 in both images.

(Note also that a translation does not include any kind of rotation.)

What is the largest possible overlap?

Example 1:

Input: A = [[1,1,0],
[0,1,0],
[0,1,0]]
B = [[0,0,0],
[0,1,1],
[0,0,1]]
Output: 3
Explanation: We slide A to right by 1 unit and down by 1 unit.

Notes:

1. 1 <= A.length = A[0].length = B.length = B[0].length <= 30
2. 0 <= A[i][j], B[i][j] <= 1

class Solution {
public:
int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
int res = 0, n = A.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
res = max(res, max(count(A, B, i, j), count(B, A, i, j)));
}
}
return res;
}
int count(vector<vector<int>>& A, vector<vector<int>>& B, int rowOffset, int colOffset) {
int sum = 0, n = A.size();
for (int i = rowOffset; i < n; ++i) {
for (int j = colOffset; j < n; ++j) {
sum += A[i][j] * B[i - rowOffset][j - colOffset];
}
}
return sum;
}
};

class Solution {
public:
int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
int res = 0, n = A.size();
vector<vector<int>> listA, listB;
unordered_map<string, int> diffCnt;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (A[i][j] == 1) listA.push_back({i, j});
if (B[i][j] == 1) listB.push_back({i, j});
}
}
for (auto a : listA) {
for (auto b : listB) {
++diffCnt[to_string(a[0] - b[0]) + "-" + to_string(a[1] - b[1])];
}
}
for (auto diff : diffCnt) {
res = max(res, diff.second);
}
return res;
}
};

class Solution {
public:
int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
int res = 0, n = A.size();
vector<int> listA, listB;
unordered_map<int, int> diffCnt;
for (int i = 0; i < n * n; ++i) {
if (A[i / n][i % n] == 1) listA.push_back(i / n * 100 + i % n);
if (B[i / n][i % n] == 1) listB.push_back(i / n * 100 + i % n);
}
for (int a : listA) {
for (int b : listB) {
++diffCnt[a - b];
}
}
for (auto diff : diffCnt) {
res = max(res, diff.second);
}
return res;
}
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/835

https://leetcode.com/problems/image-overlap/

https://leetcode.com/problems/image-overlap/discuss/177485/Java-Easy-Logic

https://leetcode.com/problems/image-overlap/discuss/130623/C%2B%2BJavaPython-Straight-Forward

https://leetcode.com/problems/image-overlap/discuss/138976/A-generic-and-easy-to-understand-method

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation