題目： LeetCode - 835. Image Overlap

題目說明

給兩個只包含 0 和 1 的正方形陣列代表圖片，求兩者經過左右、上下平移後能造成 1 重疊的最多數量。

解題思路

先使用兩個陣列紀錄兩者圖片為 1 的所有座標，接著使用 HashMap 紀錄兩張圖片任意兩個 1 的偏移量相同的個數 ( 偏移量相同代表經過同樣的平移能使得兩者都重疊 )，最後找出最大值即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B)
    {
        int n = A.size(), cnt = 0;
        vector<pair<int, int>> posA, posB; // {x, y}
        map<pair<int, int>, int> m; // {x, y}, count
        for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j)
        {
            if(A[i][j]) posA.emplace_back(i, j);
            if(B[i][j]) posB.emplace_back(i, j);
        }
        for(auto& [xA, yA] : posA) for(auto& [xB, yB] : posB) ++m[{xB - xA, yB - yA}];
        for(auto& [__, val] : m) cnt = max(cnt, val);
        return cnt;
    }
};