力扣——835. 图像重叠（Java、JavaScript、C实现）

835. 图像重叠
     给你两个图像 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，你的支持是对作者最大的鼓励，不足之处可以在评论区多多指正，交流学习