0835. Image Overlap (M)

Image Overlap (M)

题目

Two images A and B are given, represented as binary, square matrices of the same size. (A binary matrix has only 0s and 1s as values.)

We translate one image however we choose (sliding it left, right, up, or down any number of units), and place it on top of the other image. After, the overlap of this translation is the number of positions that have a 1 in both images.

(Note also that a translation does not include any kind of rotation.)

What is the largest possible overlap?

Example 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.

Notes:

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

题意

给定两个只包含0和1的矩阵，可以对矩阵进行若干次平移操作，求经过一系列平移后两个矩阵能够重叠的1的最大个数。

思路

暴力法：只考虑正向偏移(即x、y偏移量都是正数)时，共有n*n种情况，每次都统计能重叠的1的个数；而负向偏移与将另一个矩阵进行正向偏移等价。

Hash：只考虑1的位置，将两个矩阵中所有1的位置记录下来，A中的一个1只能经由一种变换平移到B中的一个1，因此我们可以维护一个HashMap，key为变换路径，value为该变换能得到的重复的1的个数。最后取其中的最大value即可。

代码实现

Java

暴力

class Solution {
    public int largestOverlap(int[][] A, int[][] B) {
        int ans = 0;
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < A.length; j++) {
                ans = Math.max(ans, shift(i, j, A, B));
                ans = Math.max(ans, shift(i, j, B, A));
            }
        }
        return ans;
    }

    private int shift(int x, int y, int[][] A, int[][] B) {
        int cnt = 0;
        for (int i = x; i < A.length; i++) {
            for (int j = y; j < A.length; j++) {
                if (A[i - x][j - y] * B[i][j] == 1) {
                    cnt++;
                }
            }
        }
        return cnt;
    }
}

Hash

class Solution {
    public int largestOverlap(int[][] A, int[][] B) {
        int ans = 0;
        Map<String, Integer> map = new HashMap<>();
        List<int[]> listA = new ArrayList<>();
        List<int[]> listB = new ArrayList<>();
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < A.length; j++) {
                if (A[i][j] == 1) {
                    listA.add(new int[] { i, j });
                }
                if (B[i][j] == 1) {
                    listB.add(new int[] { i, j });
                }
            }
        }

        for (int i = 0; i < listA.size(); i++) {
            for (int j = 0; j < listB.size(); j++) {
                int[] a = listA.get(i), b = listB.get(j);
                String key = (a[0] - b[0]) + ":" + (a[1] - b[1]);
                map.put(key, map.getOrDefault(key, 0) + 1);
                ans = Math.max(ans, map.get(key));
            }
        }

        return ans;
    }
}