- 图像重叠
给你两个图像 img1 和 img2 ，两个图像的大小都是 n x n ，用大小相同的二进制正方形矩阵表示。二进制矩阵仅由若干 0 和若干 1 组成。
转换 其中一个图像，将所有的 1 向左，右，上，或下滑动任何数量的单位；然后把它放在另一个图像的上面。该转换的 重叠 是指两个图像 都 具有 1 的位置的数目。
请注意，转换 不包括 向任何方向旋转。越过矩阵边界的 1 都将被清除。
最大可能的重叠数量是多少？
示例 1：
输入：img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
输出：3
解释：将 img1 向右移动 1 个单位，再向下移动 1 个单位。
两个图像都具有 1 的位置的数目是 3（用红色标识）。
示例 2：
输入：img1 = [[1]], img2 = [[1]]
输出：1
示例 3：
输入：img1 = [[0]], img2 = [[0]]
输出：0
Java代码：
class Solution {
public int largestOverlap(int[][] A, int[][] B) {
int n = A.length;
int[][] count = new int[n * 2 - 1][n * 2 - 1];
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
if (A[i][j] == 1)
for (int x = 0; x < n; x ++)
for (int y = 0; y < n; y ++)
if (B[x][y] == 1)
count[i - x + n - 1][j - y + n - 1] ++;
int res = 0;
for (int i = 0; i < n * 2 - 1; i ++)
for (int j = 0; j < n * 2 - 1; j ++)
res = Math.max(res, count[i][j]);
return res;
}
}
C代码：
#define DEBUG 0
#if DEBUG
#define dbg(fmt, ...) do { printf("[%s-%d]"fmt"\r\n", __FUNCTION__, __LINE__, ##__VA_ARGS__); } while (0)
#else
#define dbg(fmt, ...) do {} while (0)
#endif
int g_largestOverlap = 0;
int CalcOverlap(int** A, int ASize, int* AColSize, int** B, int BSize, int* BColSize, int x, int y)
{
int i, j;
int overlap = 0;
for (i = 0; i < ASize; i++) {
for (j = 0; j < AColSize[i]; j++) {
if ((((i + y) >= 0) && ((i + y) < ASize)) && (((j + x) >= 0) && ((j + x) < ASize))) {
dbg("i + x:%d, i + y:%d", i + x, i + y);
overlap += (B[i][j] & A[i + y][j + x]);
}
}
}
return overlap;
}
void dfs(int** A, int ASize, int* AColSize, int** B, int BSize, int* BColSize, int **visited, int x, int y)
{
int overlap;
int d[][2] = {
{ 0, 1},
{ 0, -1},
{-1, 0},
{ 1, 0}
};
int i;
int xx, yy;
overlap = CalcOverlap(A, ASize, AColSize, B, BSize, BColSize, x, y);
dbg("x:%d, y:%d, overlap:%d", x, y, overlap);
if (g_largestOverlap < overlap) {
g_largestOverlap = overlap;
dbg("g_largestOverlap:%d", g_largestOverlap);
}
for (i = 0; i < 4; i++) {
xx = x + d[i][0];
yy = y + d[i][1];
if (((xx + ASize) >= 2 * ASize) || ((xx + ASize) <= 0) ||
((yy + ASize) >= 2 * ASize) || ((yy + ASize) <= 0)) {
//dbg("xx:%d, yy:%d 2 * ASize:%d", xx, yy, 2 * ASize);
continue;
}
//dbg("xx + ASize:%d, yy + ASize:%d", xx + ASize, yy + ASize);
if (visited[yy + ASize][xx + ASize]) {
continue;
}
visited[yy + ASize][xx + ASize] = 1;
dfs(A, ASize, AColSize, B, BSize, BColSize, visited, xx, yy);
//visited[xx + ASize][yy + ASize] = 0;
}
return;
}
int largestOverlap(int** A, int ASize, int* AColSize, int** B, int BSize, int* BColSize)
{
int i;
int **visited;
g_largestOverlap = 0;
visited = malloc(ASize * 2 * sizeof(int *));
for (i = 0; i < ASize * 2; i++) {
visited[i] = malloc(ASize * 2 * sizeof(int));
memset(visited[i], 0, ASize * 2 * sizeof(int));
}
dfs(A, ASize, AColSize, B, BSize, BColSize, visited, 0, 0);
return g_largestOverlap;
}
JavaScript代码：
/**
* @param {number[][]} img1
* @param {number[][]} img2
* @return {number}
*/
var largestOverlap = function (img1, img2) {
const len = img1.length
const count = Array(2 * len + 1)
.fill(0)
.map(() => Array(2 * len + 1).fill(0))
for (let i = 0; i < len; i++) {
for (let j = 0; j < len; j++) {
if (img1[i][j] === 1) {
for (let i2 = 0; i2 < len; i2++) {
for (let j2 = 0; j2 < len; j2++) {
if (img2[i2][j2] === 1) {
count[i - i2 + len][j - j2 + len] += 1
}
}
}
}
}
}
let ans = 0
for (const row of count) {
ans = Math.max(...row, ans)
}
return ans
}
作者：KJ.JK
本文仅用于交流学习，未经作者允许，禁止转载，更勿做其他用途，违者必究。
文章对你有所帮助的话，欢迎给个赞或者 star，你的支持是对作者最大的鼓励，不足之处可以在评论区多多指正，交流学习
