图像重叠 图解题解

两张 01 方阵平移叠一起，最多对上几个 1

给两个 n×n 的 01 矩阵 img1、img2。把一张里的 1 整体往上下左右平移任意格（越界切掉、不能旋转），叠到另一张，问同一位置都是 1 的格子最多几个。例子 img1=[[1,1,0],[0,1,0],[0,1,0]]、img2=[[0,0,0],[0,1,1],[0,0,1]]，img1 向右 1、向下 1 后对上 3 个，答案 3。

把矩阵真挪一遍再逐格数，账算下来多重

枚举每种平移：横纵各挪一段，约 (2n−1)² 种；每挪一次还要把整张图 n² 个格子逐个比对、清掉出界的 1。两头一乘 O(n⁴)，还要真搬矩阵判越界，代码又长又易错。

为什么只盯着 1、根本不用真去平移

只盯着值为 1 的格子数，就能把平移和越界一起绕开。两个 1 叠加后要落到同一格，往哪挪多远完全由它俩坐标之差定死。设 img1 的 1 在 (i, j)、img2 的 1 在 (h, k)，对齐所需的平移量就是 (i−h, j−k)。枚举所有 1 配 1 各算平移量，被最多对 1 共同需要的那个，其下同时对上的 1 就最多。这个键取 img1 坐标减 img2，是把 img2 挪到 img1 所需平移的相反数——和题面向右向下差个符号，只当分组标签、正负不必纠结。

越界为什么不用管？配不上别人的 1 只有自己一票、进不了最大值，自动被排除，无需手写清零。

拿哈希表数平移量，一趟枚举定答案

实现上开一个计数器，键是平移量、值是出现次数。四重循环，外两层走 img1 每个 1 的 (i, j)、内两层走 img2 每个 1 的 (h, k)，对每一对往键 (i−h, j−k) 加一。枚举完最大值即答案，凑不出可配的 1 就返回 0。方向全程固定成 img1 减 img2，别一会儿 i−h 一会儿 h−i。

回到题面这两张图，12 对怎么数出 3

img1 的 1 在 (0,0)、(0,1)、(1,1)、(2,1)，img2 的在 (1,1)、(1,2)、(2,2)，共 12 对。逐对算平移量（img1 减 img2）：(0,0) 得 (−1,−1)、(−1,−2)、(−2,−2)；(0,1) 得 (−1,0)、(−1,−1)、(−2,−1)；(1,1) 得 (0,0)、(0,−1)、(−1,−1)；(2,1) 得 (1,0)、(1,−1)、(0,−1)。

归堆后 (−1,−1) 出现在 (0,0)配(1,1)、(0,1)配(1,2)、(1,1)配(2,2) 三处，(0,−1) 两次，余各一次。最大计数 3，即按 (−1,−1) 叠有三对 1 同时对上，答案 3。

四重循环的开销，和几种一票就出局的输入

复杂度上，最坏整图全 1，两图各 n² 个 1 两两配对约 n²×n² 次，时间 O(n⁴)，只枚举 1 远小于上界。计数器存不同平移量，上界约 (2n−1)²，空间 O(n²)。

边界：单格 [[1]]、[[1]] 唯一平移量 (0,0) 计数 1；某张全 0 配不出对、返回 0；两图有 1 却对不齐，各平移量一票、最大计数 1；空计数器直接取最大值会报错，先判空返回 0。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        n = len(img1)
        cnt = Counter()
        for i in range(n):
            for j in range(n):
                if img1[i][j]:
                    for h in range(n):
                        for k in range(n):
                            if img2[h][k]:
                                cnt[(i - h, j - k)] += 1
        return max(cnt.values()) if cnt else 0

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
        int n = img1.size();
        map<pair<int, int>, int> cnt;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (img1[i][j]) {
                    for (int h = 0; h < n; ++h) {
                        for (int k = 0; k < n; ++k) {
                            if (img2[h][k]) {
                                ans = max(ans, ++cnt[{i - h, j - k}]);
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int largestOverlap(int[][] img1, int[][] img2) {
        int n = img1.length;
        Map<List<Integer>, Integer> cnt = new HashMap<>();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (img1[i][j] == 1) {
                    for (int h = 0; h < n; ++h) {
                        for (int k = 0; k < n; ++k) {
                            if (img2[h][k] == 1) {
                                List<Integer> t = Arrays.asList(i - h, j - k);
                                ans = Math.max(ans, cnt.merge(t, 1, Integer::sum));
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
}