835. Image Overlap

Medium

You are given two images, img1 and img2, represented as binary, square matrices of size n x n. A binary matrix has only 0s and 1s as values.

We translate one image however we choose by sliding all the 1 bits left, right, up, and/or down any number of units. We then place it on top of the other image. We can then calculate the overlap by counting the number of positions that have a 1 in both images.

Note also that a translation does not include any kind of rotation. Any 1 bits that are translated outside of the matrix borders are erased.

Return the largest possible overlap.

Example 1:

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output:
 3
Explanation:
 We translate img1 to right by 1 unit and down by 1 unit.

The number of positions that have a 1 in both images is 3 (shown in red).

Example 2:

Input: img1 = [[1]], img2 = [[1]]
Output:
 1

Example 3:

Input: img1 = [[0]], img2 = [[0]]
Output:
 0

Constraints:

• n == img1.length == img1[i].length

• n == img2.length == img2[i].length

• 1 <= n <= 30

• img1[i][j] is either 0 or 1.

• img2[i][j] is either 0 or 1.

解題

這題原本只想得到暴力解，但在討論區看到很棒的方法。雖然時間複雜度還是偏高，但程式碼優美好理解。大家可以點進上面討論區連結，或是看這個影片，講解得非常清楚。

Runtime: 84 ms, faster than 50.00%

Memory Usage: 6.1 MB, less than 50.00%

下方之所以用 i*100+j 來記錄 (x, y) ，而不是用二維陣列或 struct 紀錄是因為題目有限制正方形邊長最大為 30 。

func largestOverlap(img1 [][]int, img2 [][]int) int {
    length := len(img1)
    
    arr1 := make([]int, 0)
    arr2 := make([]int, 0)
    
    for i:= 0; i<length; i++ {
        for j:=0; j<length; j++ {
            if img1[i][j]==1 { arr1 = append(arr1, i*100+j) }
            if img2[i][j]==1 { arr2 = append(arr2, i*100+j) }
        }
    }
    
    count := make(map[int]int)
    ans := 0
    
    for i:=0; i<len(arr1); i++ {
        for j:=0; j<len(arr2); j++ {
            count[arr1[i]-arr2[j]]++
            if count[arr1[i]-arr2[j]] > ans {
                ans = count[arr1[i]-arr2[j]]
            }
        }
    }
    
    return ans
}