Leecode #835 图像重叠

难度：medium

给出两个图像 A 和 B ，A 和 B 为大小相同的二维正方形矩阵。（并且为二进制矩阵，只包含0和1）。

我们转换其中一个图像，向左，右，上，或下滑动任何数量的单位，并把它放在另一个图像的上面。之后，该转换的重叠是指两个图像都具有 1 的位置的数目。

（请注意，转换不包括向任何方向旋转。）

最大可能的重叠是什么？

示例

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

解题思路

类似图像卷积的算法，直接暴力枚举

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        l = len(A)
        if l == 1:
            return A[0][0] * B[0][0]
            
        rlt = 0
        for i in range(-l+1,l-1): # 稍微简化一下
            for j in range(-l+1,l-1):
                rlt = max(rlt, self.multiple(A,B,i,j))
        return rlt
    def multiple(self, a, b, offsetx=0, offsety=0):
        l = len(a)
        rlt = 0
        for i in range(l):
            for j in range(l):
                ii = i+offsetx
                jj = j+offsety
                if  ii>=0 and ii< l and jj<l and jj >=0:
                        rlt += a[ii][jj]*b[i][j]
        return rlt

过了时间限制但是复杂度很高，执行时间大概为2600ms，进一步优化可以从multiple限制ij的取值

    def multiple(self, a, b, offsetx=0, offsety=0):
        l = len(a)
        rlt = 0

        begin_i = 0 if offsetx>0 else -offsetx
        begin_j = 0 if offsety>0 else -offsety

        end_i = l if offsetx<0 else l - offsetx
        end_j = l if offsety<0 else l - offsety

        for i in range(begin_i, end_i):
            for j in range(begin_j, end_j):
                rlt += a[i+offsetx][j+offsety]*b[i][j]
        return rlt

执行时间为880ms，看到有人的结果只花了400ms应该还可以进一步优化，不过暂时想不出了。