835,Image Overlap

835.Image Overlap

给出两个图像 A 和 B ，A 和 B 为大小相同的二维正方形矩阵。（并且为二进制矩阵，只包含0和1）。 我们转换其中一个图像，向左，右，上，或下滑动任何数量的单位，并把它放在另一个图像的上面。之后，该转换的重叠是指两个图像都具有 1 的位置的数目。 （请注意，转换不包括向任何方向旋转。） 最大可能的重叠是什么？

• 示例 1:

输入：A = [[1,1,0],
          [0,1,0],
          [0,1,0]]
     B = [[0,0,0],
          [0,1,1],
          [0,0,1]]
输出：3
解释: 将 A 向右移动一个单位，然后向下移动一个单位。

• 注意:

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

方法：因为AB矩阵长度都不大，所以直接遍历所有位置找到最大值。

1. 创建一个函数得到将一个矩阵经过（x,y）平移后的矩阵。

2. 创建一个函数得到两个矩阵中相同位置上都为1的个数。

3. 平移范围为(-n,n)，对矩阵A进行平移，每次平移后与B得到当前的overlap值，并更新最大值。

4. 遍历完成，所得到的最大值即为结果。

class Solution {
public:
    int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
        int lapmax=overlap(A,B);
        int n=A.size();
        vector<vector<int>> AA(n,vector<int>(n,0));

        for(int i=-n;i<n;i++)
            for(int j=-n;j<n;j++)
            {
                AA=move(A,i,j);
                int temp= overlap(AA,B);
                if (temp>lapmax)
                    lapmax=temp;
            }
        return lapmax;
    }
private:
    vector<vector<int>> move(vector<vector<int>> &A,int x,int y)
    {
        int n=A.size();
        vector<vector<int>> AA(n,vector<int>(n,0));
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            {
                if(A[i][j] && (x+i) >=0 && x+i <n && y+j >=0 && y+j <n)
                    AA[i+x][j+y] =1;
            }
        return AA;
    }
    int overlap(vector<vector<int>>& A, vector<vector<int>>&B)
    {
        int n=A.size(),num=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                if(A[i][j] && B[i][j])
                    num++;
        return num;
    }
};