给出两个图像 A 和 B ,A 和 B 为大小相同的二维正方形矩阵。(并且为二进制矩阵,只包含0和1)。 我们转换其中一个图像,向左,右,上,或下滑动任何数量的单位,并把它放在另一个图像的上面。之后,该转换的重叠是指两个图像都具有 1 的位置的数目。 (请注意,转换不包括向任何方向旋转。) 最大可能的重叠是什么?
Copy 输入:A = [[1,1,0],
[0,1,0],
[0,1,0]]
B = [[0,0,0],
[0,1,1],
[0,0,1]]
输出:3
解释: 将 A 向右移动一个单位,然后向下移动一个单位。
Copy 1 <= A.length = A[0].length = B.length = B[0].length <= 30
0 <= A[i][j], B[i][j] <= 1
Copy 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;
}
};