You are given two images, img1
and img2
, represented as binary, square matrices of size n x n
. A binary matrix has only 0
s and 1
s as values.
We translate one image however we choose by sliding all the 1
bits left, right, up, and/or down any number of units. We then place it on top of the other image. We can then calculate the overlap by counting the number of positions that have a 1
in both images.
Note also that a translation does not include any kind of rotation. Any 1
bits that are translated outside of the matrix borders are erased.
Return the largest possible overlap.
Example 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. The number of positions that have a 1 in both images is 3 (shown in red).
Example 2:
Input: img1 = [[1]], img2 = [[1]] Output: 1
Example 3:
Input: img1 = [[0]], img2 = [[0]] Output: 0
Constraints:
n == img1.length == img1[i].length
n == img2.length == img2[i].length
1 <= n <= 30
img1[i][j]
is either0
or1
.img2[i][j]
is either0
or1
.
Solution: Hashtable of offsets
Enumerate all pairs of 1 cells (x1, y1) (x2, y2), the key / offset will be ((x1-x2), (y1-y2)), i.e how should we shift the image to have those two cells overlapped. Use a counter to find the most common/best offset.
Time complexity: O(n4) Note: this is the same as brute force / simulation method if the matrix is dense.
Space complexity: O(n2)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) { const int n = img1.size(); unordered_map<int, int> m; for (int y1 = 0; y1 < n; ++y1) for (int x1 = 0; x1 < n; ++x1) if (img1[y1][x1]) for (int y2 = 0; y2 < n; ++y2) for (int x2 = 0; x2 < n; ++x2) if (img2[y2][x2]) ++m[(x1 - x2) * 100 + (y1 - y2)]; int ans = 0; for (const auto [key, count] : m) ans = max(ans, count); return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment