文件详细信息

下载本文件

本文件的大小为 1468 字节。

#include<cstdio>
#include<cstring>
inline void chkmax(int&a,const int b){
	a<b&&(a=b);
}
inline void chkmin(int&a,const int b){
	a>b&&(a=b);
}
inline int max(const int a,const int b){
	return a>b?a:b;
}
inline int min(const int a,const int b){
	return a<b?a:b;
}
const int maxn=500,maxn2=maxn*maxn;
int n,n2,k,cnt,l[maxn2],r[maxn2],u[maxn2],d[maxn2],arr[maxn+1][maxn+1];
int main(){
	scanf("%d%d",&n,&k),n2=n*n;
	memset(l,0x3f,sizeof(int)*n2);
	memset(u,0x3f,sizeof(int)*n2);
	for(int i=0;i<n;i++)
		for(int j=0,val;j<n;j++){
			scanf("%d",&val),val--;
			if(l[val]==0x3f3f3f3f)cnt++;
			chkmin(l[val],i);
			chkmax(r[val],i);
			chkmin(u[val],j);
			chkmax(d[val],j);
		}
	if(cnt<=k)printf("%d\n",k-cnt);
	else{
		for(int len=1;len<=n;len++){
			const int lim=n-len+1;
			for(int i=0;i<=lim;i++)memset(arr[i],0,sizeof(int)*(lim+1));
			for(int val=0,_l,_r,_u,_d;val<n2;val++){
				if(l[val]==0x3f3f3f3f)continue;
				_l=max(r[val]-len+1,0),_r=min(l[val]+1,lim);
				if(_l<_r){
					_u=max(d[val]-len+1,0),_d=min(u[val]+1,lim);
					if(_u<_d){
						arr[_l][_u]++,arr[_r][_u]--;
						arr[_l][_d]--,arr[_r][_d]++;
					}
				}
			}
			for(int i=0;i<lim;i++)
				for(int j=1;j<lim;j++)
					arr[i][j]+=arr[i][j-1];
			for(int i=1;i<lim;i++)
				for(int j=0;j<lim;j++)
					arr[i][j]+=arr[i-1][j];
			for(int i=0;i<lim;i++)
				for(int j=0;j<lim;j++)
					if(cnt-arr[i][j]==k||cnt-arr[i][j]==k-1){
						puts("1");
						return 0;
					}
		}
		puts("2");
	}
	return 0;
}