# 835.Image-Overlap

## 835. Image Overlap

## 题目地址

<https://leetcode.com/problems/image-overlap/>

## 题目描述

```
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
```

## 代码

### Approach #0

```java
public int largestOverlap(int[][] A, int[][] B) {
    int N = A.length;
    List<Integer> LA = new ArrayList<>(),  LB = new ArrayList<>();
    HashMap<Integer, Integer> count = new HashMap<>();
    for (int i = 0; i < N * N; ++i)
        if (A[i / N][i % N] == 1)
            LA.add(i / N * 100 + i % N);
    for (int i = 0; i < N * N; ++i)
        if (B[i / N][i % N] == 1)
            LB.add(i / N * 100 + i % N);
    for (int i : LA) for (int j : LB)
            count.put(i - j, count.getOrDefault(i - j, 0) + 1);
    int res = 0;
    for (int i : count.values())
        res = Math.max(res, i);
    return res;
}
```

### Approach #1 Translate by Delta Confusion

Time: O(N^6) && Space: O(N^2)

```java
import java.awt.Point;

class Solution {
  public int largestOverlap(int[][] A, int[][] B) {
        int N = A.length;
    List<Point> A2 = new ArrayList();
    List<Point> B2 = new ArrayList();
    for (int i = 0; i < N * N; i++) {
      if (A[i/N][i%N] == 1) {
        A2.add(new Point(i/N, i%N));
      }
      if (B[i/N][i%N] == 1) {
        B2.add(new Point(i/N, i%N));
      }
    }

    Set<Point> Bset = new HashSet(B2);

    int ans = 0;
    Set<Point> seen = new HashSet();
    for (Point a: A2) {
      for (Point b: B2) {
        Point delta = new Point(b.x - a.x, b.y - a.y); // 相同的图案, 对应点的delta相同
        if (!seen.contains(delta)) {
          seen.add(delta);
          int cand = 0;
          for (Point p: A2) {
            if (Bset.contains(new Point(p.x + delta.x, p.y + delta.y))) {
              cand++;
            }
          }
          ans = Math.max(ans, cand);
        }
      }
    }

    return ans;
  }
}
```

### Approach #2 Count by Delta

```java
class Solution {
  public int largestOverlap(int[][] A, int[][] B) {
    int N = A.length;
    int[][] count = new int[2 * N + 1][2 * N + 1];
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        if (A[i][j] == 1) {
          for (int i2 = 0; i2 < N; i2++) {
            for (int j2 = 0; j2 < N; j2++) {
              if (B[i2][j2] == 1) {
                count[i-i2+N][j-j2+N] += 1;
              }
            }
          }
        }
      }
    }
    int ans = 0;
    for (int[] row: count) {
      for (int v: row) {
        ans = Math.max(ans, v);
      }
    }
    return ans;
  }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/matrix/835.image-overlap.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.