LeetCode(835) - 图像重叠

题目描述

给出两个图像 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. 1 <= A.length = A[0].length = B.length = B[0].length <= 30
  2. 0 <= A[i][j], B[i][j] <= 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/contains-duplicate-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

设图片的长宽为 N，只移动 A 不移动 B，为了覆盖到所有情况，A 横向和纵向的移动范围都是 [-(N-1), N-1]，假设 A 移动向量为 (x, y), x, y ∈ [-(N-1), N-1]，则图像 A 的有效范围为 [asx, asy] ~ [aex, aey]，图像 B 的有效范围为 [bsx, bsy] ~ [bex, bey]，其中：

asx = bsx - x;
asy = bsy - y;
aex = bex - x;
aey = bey - y;

bsx = max(0, x);
bsy = max(0, y);
bex = min(N - 1 + x, N - 1);
bey = min(N - 1 + y, N - 1);

设 (i, j) 为图像 B 有效范围内的一点，则其对应图像 A 上的点为 (i - x, j - y)。

我们要做的就是遍历所有 (x, y)（这需要两层循环），然后在循环里边再遍历所有有效范围内的点（又需要两层循环），在最里层循环中统计重叠的点数，找到所有 (x, y) 中最大的重叠数，就是最后的结果

class Solution {
    public int largestOverlap(int[][] A, int[][] B) {
        int N = A.length;
        int N_1 = N - 1;
        int res = 0;

        for (int x = -N_1; x <= N_1; x++) {
            for (int y = -N_1; y <= N_1; y++) {
                int bsx = Math.max(0, x);
                int bex = Math.min(N_1 + x, N_1);
                int bsy = Math.max(0, y);
                int bey = Math.min(N_1 + y, N_1);

                // 减5ms
                if ((bex - bsx + 1) * (bey - bsy + 1) <= res) {
                    continue;
                }

                int count = 0;
                for (int i = bsx; i <= bex; i++) {
                    for (int j = bsy; j <= bey; j++) {
                        if (B[i][j] == 1 && A[i - x][j - y] == 1) {
                            count++;
                        }
                    }
                }
                res = Math.max(res, count);
            }
        }

        return res;
    }
}