[信息与未来 2023] 图像重建
题意理解
给出两张图，每张图的第一行两个数表示行列数量，两张图之间空一行。
两张图可以任意平移，求平移后完全重合的最多格点数。
思路阐述
直接暴力寻找，先固定一张图，再将另一张的四个角对上来，按照对上来这张图的方向遍历每一个点。
如图：蓝色点是基础点，黑色是基础图，红色是另一张图，绿色是遍历方向。
左上角
右下角
左下角
右上角
具体方法：遍历第一张图的每一个点，再以这个点为基础，将第二张图的左上角、左下角、右上角、右下角分别对应上去搜索。当然还要以第二张图为基础用同样的方式再遍历一次。
优化：因为两张图必须完全重合才在答案考虑范围内，所以只要有一格不对应即可直接退出这种情况。
代码呈现
#include <bits/stdc++.h>
using namespace std;
int a,b;//第一张图的行列
int c,d;//第二张
bool mp1[55][55];//图一
bool mp2[55][55];//图二
int x;//辅助输入
int ans,cnt;//计数
bool f;//标记是否在重合范围内各个格子都相同
string s;//吃掉中间的空行
signed main(){
scanf("%d%d",&a,&b);
for (int i=1;i<=a;i++)
for (int j=1;j<=b;j++){
scanf("%d",&x);
if (x) mp1[i][j]=1;
}
getline(cin,s);//吃掉中间的空行
scanf("%d%d",&c,&d);
for (int i=1;i<=c;i++)
for (int j=1;j<=d;j++){
scanf("%d",&x);
if (x) mp2[i][j]=1;
}
for (int i=1;i<=a;i++)
for (int j=1;j<=b;j++){//遍历图一
cnt=0;
f=1;//初始化变量
for (int k=1;k<=c;k++){
if (i+k>a) break;//注意遍历图二时不要超图一范围
for (int l=1;l<=d;l++){//对应左上角
if (j+l>b) break;
if (mp1[i+k][j+l]==mp2[k][l]){
cnt++;//相同
}
else{
f=0;//不同，标记
break;//退出
}
}
if (!f) break;//有不同的，退出
}
if (f) ans=max(ans,cnt);//没有问题，取最大值
cnt=0;
f=1;
for (int k=c;k>=1;k--){
if (i-(c-k)<1) break;
for (int l=d;l>=1;l--){//右下角
if (j-(d-l)<1) break;
if (mp1[i-(c-k)][j-(d-l)]==mp2[k][l]){
cnt++;
}
else{
f=0;
break;
}
}
if (!f) break;
}
if (f) ans=max(ans,cnt);
cnt=0;
f=1;
for (int k=c;k>=1;k--){
if (i-(c-k)<1) break;
for (int l=1;l<=d;l++){//右上角
if (j+l>b) break;
if (mp1[i-(c-k)][j+l]==mp2[k][l]){
cnt++;
}
else{
f=0;
break;
}
}
if (!f) break;
}
if (f) ans=max(ans,cnt);
cnt=0;
f=1;
for (int k=1;k<=c;k++){
if (i+k>a) break;
for (int l=d;l>=1;l--){//左下角
if (j-(d-l)<1) break;
if (mp1[i+k][j-(d-l)]==mp2[k][l]){
cnt++;
}
else{
f=0;
break;
}
}
if (!f) break;
}
if (f) ans=max(ans,cnt);
}
for (int i=1;i<=c;i++)
for (int j=1;j<=d;j++){//以第二张图为基础的遍历
cnt=0;
f=1;
for (int k=1;k<=a;k++){
if (i+k>c) break;
for (int l=1;l<=b;l++){
if (j+l>d) break;
if (mp1[k][l]==mp2[k+i][l+j]){
cnt++;
}
else{
f=0;
break;
}
}
if (!f) break;
}
if (f) ans=max(ans,cnt);
cnt=0;
f=1;
for (int k=a;k>=1;k--){
if (i-(a-k)<1) break;
for (int l=b;l>=1;l--){
if (j-(b-l)<1) break;
if (mp1[k][l]==mp2[i-(a-k)][j-(b-l)]){
cnt++;
}
else{
f=0;
break;
}
}
if (!f) break;
}
if (f) ans=max(ans,cnt);
cnt=0;
f=1;
for (int k=1;k<=a;k--){
if (i+k>c) break;
for (int l=b;l>=1;l--){
if (j-(b-l)<1) break;
if (mp1[k][l]==mp2[i+k][j-(b-l)]){
cnt++;
}
else{
f=0;
break;
}
}
if (!f) break;
}
if (f) ans=max(ans,cnt);
cnt=0;
f=1;
for (int k=a;k>=1;k--){
if (i-(a-k)<1) break;
for (int l=1;l<=b;l--){
if (j+l>d) break;
if (mp1[k][l]==mp2[i-(a-k)][j+l]){
cnt++;
}
else{
f=0;
break;
}
}
if (!f) break;
}
if (f) ans=max(ans,cnt);
}
printf("%d",ans);//输出
return 0;
}希望可以帮到各位大佬。