C++刷LeetCode（835. 图像重叠）【数学】

糖逗

题目描述：

1. 给出两个图像 A 和 B ，A 和 B 为大小相同的二维正方形矩阵。（并且为二进制矩阵，只包含0和1）。
   
2. 
   
3. 我们转换其中一个图像，向左，右，上，或下滑动任何数量的单位，并把它放在另一个图像的上面。之后，该转换的重叠是指两个图像都具有 1 的位置的数目。
   
4. 
   
5. （请注意，转换不包括向任何方向旋转。）
   
6. 
   
7. 最大可能的重叠是什么？
   
8. 
   
9. 示例 1:
   
10. 
    
11. 输入：A = [[1,1,0],
    
12.           [0,1,0],
    
13.           [0,1,0]]
    
14.      B = [[0,0,0],
    
15.           [0,1,1],
    
16.           [0,0,1]]
    
17. 输出：3
    
18. 解释: 将 A 向右移动一个单位，然后向下移动一个单位。
    
19. 注意: 
    
20. 
    
21. 1 <= A.length = A[0].length = B.length = B[0].length <= 30
    
22. 0 <=&#160;A[i][j], B[i][j] <= 1
    
23. 
    
24. 来源：力扣（LeetCode）
    
25. 链接：https://leetcode-cn.com/problems/image-overlap
    
26. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int flatten(int x, int y){
   
4.         return (x << 6) + y;//二维坐标通过这个函数一一映射，这个函数并不唯一
   
5.     }
   
6.     int largestOverlap(const vector<vector<int>>& A, const vector<vector<int>>& B) {
   
7.         int res = 0;
   
8.         vector<int>store1, store2;
   
9.         map<int, int>same_distance;
   
10.         for(int i = 0; i < A.size(); i++){
    
11.             for(int j = 0; j < A[0].size(); j++){
    
12.                 if(A[i][j])store1.push_back(flatten(i, j));
    
13.                 if(B[i][j])store2.push_back(flatten(i, j));
    
14.             }
    
15.         }
    
16.         for(auto cha1 : store1){
    
17.             for(auto cha2 : store2){
    
18.                 same_distance[cha1 - cha2]++;
    
19.             }
    
20.         }
    
21.         for(auto cha : same_distance){
    
22.             res = max(res, cha.second);
    
23.         }
    
24.         return res;
    
25.     }
    
26. };

复制代码

参考链接：https://leetcode-cn.com/problems ... chi-ji-shu-by-hare/