0835. Image Overlap

题目信息

题号:

0835

难度:

Medium

主题:

二进制矩阵、平移、重叠计数

原题:

LeetCode 0835

重点:

只能把其中一幅图按整数行列平移,不能旋转;移出边界的部分舍弃,重叠只统计同一位置均为 1 的格子

题目重述

给定两个大小相同的 n x n 二进制矩阵 img1 和 img2。可以把其中一幅图像向上、下、左或右平移任意整数格,平移过程中不能旋转;移出矩阵范围的 1 会被舍弃。

一次平移后的重叠值,是两个矩阵在相同位置上都为 1 的格子数量。请返回所有可能平移方式中能够取得的最大重叠值。

1 <= n <= 30,两个矩阵的元素都只可能为 0 或 1。

自建示例

平移后使两个单点重合:

输入:img1 = [[1,0],[0,0]], img2 = [[0,0],[0,1]]
输出:1
解释:把 img1 向下、向右各平移一格后,它的唯一一个 1 与 img2 右下角的 1 重合,最大重叠值为 1。

其中一幅图没有任何一:

输入:img1 = [[0,0],[0,0]], img2 = [[1,0],[0,1]]
输出:0
解释:无论怎样平移,全零的 img1 都不会在任何位置提供值 1,因此不可能产生重叠,最大值为 0。