题目链接：https://leetcode.cn/problems/image-overlap/

题目大意：给出两个位图矩阵img1[][]和img2[][]，其中元素只有0和1。一次平移是指将一个图像里【所有的1】都向左/右/上/下移动一格。求经过若干次平移后，两个图像能重叠的1的最多个数是多少。

思路：用一个pair<int, int> diff来表示若干次的平移（或者我们称为，一种平移），其实就是求两个图像的1之间，哪种平移的数量最多。找到两个图像所有的1，进行遍历即可。

【注意】虽然有些题目说可以将二维矩阵转换成一维来做，但我这样尝试时发现是有些不对的。比如img1[][]中第$i$行末尾的元素，和img2[][]中第$i+1$行第一个元素，做差得到的是-1。但img1[][]中第$i$行倒数第二个元素，和img2[][]中第$i$行最后一个元素，做差也是-1。但显然这两种平移是不同的，我认为仅用一维来表示平移是不够的。上述两种平移用二维表示分别是(-n, 1)和(1, 0)，一个是先向左n格，再向下1格；另一个则是向右移动1格。

因此老老实实用二维表示平移向量做。

完整代码

class Solution {
public:int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {int N = img1.size();vector<pair<int, int>> ones1;map<pair<int, int>, int> diff2cnt;for (int i = 0; i < img1.size(); i++) {for (int j = 0; j < img1[0].size(); j++) {if (img1[i][j])ones1.push_back(make_pair(i, j));}} for (int i = 0; i < img2.size(); i++) {for (int j = 0; j < img2[0].size(); j++) {if (img2[i][j]) {for (auto coord : ones1) {auto diff = make_pair(i - coord.first, j - coord.second);if (diff2cnt.find(diff) == diff2cnt.end())diff2cnt[diff] = 1;elsediff2cnt[diff]++;}}   }} int ret = 0;for (auto it = diff2cnt.begin(); it != diff2cnt.end(); it++)ret = max(ret, it->second);return ret;}
};