B3788 [信息与未来 2023] 图像重建题解

· · 题解

B3788 题解

题目传送门

题目大意：

给你两张图它们可以随意的平移，求平移后完全重合的最多格点数。

思路：

首先看到说明提示。

对于百分之一百的的数据，满足 1 \le n,m \le 50 我们就可以想到用暴力枚举的方法。其实是我是蒟蒻想不到其他办法了。

那我们要怎么搜呢？分别枚举图 2 的 x 和 y 轴再和图 1 来对比就行了。

都快看完了点点赞吧。

最期待的代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 55;
int n1, n2, m1, m2, res = -0x3f;//第一张图和第二张图的n和m,res是重合的最大值;
bool xy1[N][N], xy2[N][N];//第一张图和第二张图的像素;

int main() {
//读入数据;
    cin >> n1 >> m1;
    for(int i = 1;i <= n1;i++)
        for (int j = 1;j <= m1;j++)
            cin >> xy1[i][j];
    cin >> n2 >> m2;
    for(int i = 1;i <= n2;i++)
        for(int j = 1;j <= m2;j++)
            cin >> xy2[i][j];
//开始暴力枚举;
for(int dx = -n1;dx <= n1;dx++)//枚举x轴移动方向
    for(int dy = -m1;dy <= m1;dy++){//枚举y轴移动方向
    int ans = 0,f = 1;
    for(int i = 1;i <= n2;i++)//扫数组
        for(int j = 1;j <= m2;j++){
        int nx = i + dx,ny = j + dy;
        if(nx > 0 && nx <= n1 && ny > 0 && ny <= m1) {
            if(xy1[nx][ny] == xy2[i][j]) ans++;
            else f = 0;//有不同的直接清零;
        }
    }
    res = max(res, ans * f);
}
cout << res << endl;
    return 0;//完美结束;
}