题目描述

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

我们转换其中一个图像，向左，右，上，或下滑动任何数量的单位，并把它放在另一个图像的上面。之后，该转换的重叠是指两个图像都具有 1 的位置的数目。
（请注意，转换不包括向任何方向旋转。）
最大可能的重叠是什么？

样例

Input: A = [[1,1,0],
            [0,1,0],
            [0,1,0]]
       B = [[0,0,0],
            [0,1,1],
            [0,0,1]]
Output: 3
Explanation: We slide A to right by 1 unit and down by 1 unit.

算法1

(剪枝温柔の枚举) $O(A*B + N^2)$

Python3 代码

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        N = len(A)
        LA = [i // N * 100 + i % N for i in range(N * N) if A[i // N][i % N]]
        LB = [i // N * 100 + i % N for i in range(N * N) if B[i // N][i % N]]
        c = collections.Counter(i - j for i in LA for j in LB)
        return max(c.values() or [0])```

Assume A the number of points in the image A
B the number of points in the image B,
N = A.length = B.length.
$O(N^2)$ time for preparing,
and $O(AB)$ time for loop.

Q & A

或者叫FAQ
Q: why 100?
100 is big enough and very clear.
For example, If I slide 13 rows and 19 cols, it will be 1319.

Q: why not 30?
30 is not big enough.
For example: 409 = 13 * 30 + 19 = 14 * 30 - 11.
409 can be taken as sliding “14 rows and -11 cols” or “13 rows and 19 cols” at the same time.

Q: How big is enough?
Bigger than 2N - 1.
Bigger than 2N - 1.
Bigger than 2N - 1.

Q: Can we replace i / N * 100 + i % N by i?
No, it’s wrong for simple test case [[0,1],[1,1]], [[1,1],[1,0]]
摘自LC评论区lee大神