题意 给出k块地 规模n*m 需要在每块地中找至多一块h*w的地 这些地中如果包含字母 只能包含一种字母 如果一块地中选地使用了A 其余的地就不能使用A 但是全0可以重复
问 最后能最多选出来多少块地
因为每次选地的唯一 和 字母覆盖的唯一 可以很容易的想到二分图
暴力把每块地能够选地的类型找出来 形成关系矩阵 建图后 二分图的A区是选的地 B区是所有可以选的字母
需要注意的是 既然全0的区域是可以多次选择的 那么 如果一块地可以选出全0的区域 就直接不管他 考虑二分图的时候 直接跳过
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<iostream>
#include<vector>
using namespace std;
int r,n,m,h,w;
bool g[100][100];
char s[500][500];
bool vis[500];
int linker[500];
bool jiaru[500];
bool fin(int u)
{
for(int i=1; i<30; i++)
{
if(g[u][i])
{
if(vis[i])
{
vis[i]=false;
if(linker[i]==-1||fin(linker[i]))
{
linker[i]=u;
return true;
}
}
}
}
return false;
}
int xyl()
{
int tot=0;
memset(linker,-1,sizeof(linker));
for(int i=1; i<=r; i++)
{
if(jiaru[i])
continue;
memset(vis,true,sizeof(vis));
if(fin(i))
tot++;
}
return tot;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int ans=0;
memset(g,false,sizeof(g));
memset(jiaru,false,sizeof(jiaru));
scanf("%d%d%d%d%d",&r,&n,&m,&h,&w);
for(int i=1; i<=r; i++)
{
for(int k=1; k<=n; k++)
scanf("%s",s[k]+1);
for(int k=1; k<=n-h+1; k++)
{
if(jiaru[i])
break;
for(int j=1; j<=m-w+1; j++)
{
int many=0;
char f='0';
for(int l=k; l<=k+h-1; l++)
{
for(int o=j; o<=j+w-1; o++)
{
if(s[l][o]!='0')
{
if(s[l][o]!=f)
{
many++;
f=s[l][o];
}
}
}
}
if(many==1)
{
int sz=(f-'A')+1;
g[i][sz]=true;
}
else if(many==0)
{
jiaru[i]=true;
ans++;
break;
}
}
}
}
int res=xyl();
printf("%d\n",ans+res);
}
}