A.P4398 [JSOI2008]Blue Mary的战役地图
- 考场写了个暴力，我还以为要挂了，
结果这题暴力可过；
Solution
-
本来想写 \(\mathtt{O(n^6)}\) 的暴力，但感觉可能过不了，所以加了亿点小优化；
-
我把第一张地图（记为 \(a\)）里的所有数字进行了离散化，开了一个 \(\mathtt{vector}\) 来存每个值在第二张地图（记为 \(b\)）里对应的坐标，就避免了 \(\mathtt{n^4}\) 的枚举；
-
然后枚举 \(a\) 中正方形的左上角坐标，枚举在 \(b\) 中对应的点坐标，再枚举正方形边长。一旦出现越界或是不同就弹出。
-
最后加了一个小优化，就是当当前枚举的 \(a\) 坐标已经不足以产生一个边长大于 \(ans\) 的正方形时，直接弹出；
AC code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
s=s*10+int(ch-'0');
ch=getchar();
}
return s*f;
}
const int N=55;
#define re register
struct memr{
int x,y;
};
int n;
int a[N][N],b[N][N];
int c[N*N],tot=0;
int cl;
vector<memr>nxt[N*N];
inline int rk(int x){
return lower_bound(c+1,c+cl+1,x)-c;
}
int main(){
// freopen("map.in","r",stdin);
// freopen("map.out","w",stdout);
n=read();
for(re int i=1;i<=n;++i)
for(re int j=1;j<=n;++j){
a[i][j]=read();
c[++tot]=a[i][j];
}
sort(c+1,c+tot+1);
cl=unique(c+1,c+tot+1)-c-1;
for(re int i=1;i<=n;++i)
for(re int j=1;j<=n;++j){
b[i][j]=read();
nxt[rk(b[i][j])].push_back((memr){i,j});
}
int ans=0;
for(re int i=1;i<=n;++i){
for(re int j=1;j<=n;++j){
int r=rk(a[i][j]);
for(re int k=0;k<nxt[r].size();++k){
int x=nxt[r][k].x;
int y=nxt[r][k].y;
int cnt=0;
bool s=1;
while(s){
++cnt;
if(x+cnt-1>n || y+cnt-1>n) break;
if(i+cnt-1>n || j+cnt-1>n) break;
for(re int p=x,q=i;p<x+cnt;++p,++q)
if(a[q][j+cnt-1]!=b[p][y+cnt-1]){
s=0;
break;
}
for(re int p=y,q=j;p<y+cnt-1 && s;++p,++q)
if(a[i+cnt-1][q]!=b[x+cnt-1][p]){
s=0;
break;
}
}
ans=max(ans,cnt-1);
}
if(ans>n-j+1)
break;
}
if(ans>n-i+1)
break;
}
printf("%d",ans);
return 0;
}