快要比赛了 看看原来做过的题 感觉这道题当时做的还是挺费劲的 所以发一下
题意：
一个土豪要建别墅 因为有的地区地方不够大 所以要拆屋子
每个地方的字母就是对应开发商的地盘
没有字母的就是自由土地
一个开发商的土地只能拆一次
一片土地只能建一个别墅
问最多能建几个别墅
思路：
建图之后直接跑算法……
坑点是如果直接可以建别墅 就不用跑算法直接+1……
而且一片土地只能建一个别墅……
算法还是很模板的
（PS：代码太长风格不好的话真的没有可读性-_-||）
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<queue>
#define M(a,b) memset(a,b,sizeof(a))
#define ll long long
using namespace std;
const int inf=0x3f3f3f;
int linker[];
bool zimu[];
int match[][];
bool visy[],vis[][];
bool jump[];
bool find_(int a)
{
for(int i=; i<; i++)
{
if(match[a][i]==&&visy[i]==)
{
visy[i]=;
if(linker[i]==||find_(linker[i]))
{
linker[i]=a;
return true;
}
}
}
return false;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
M(jump,);
M(linker,);
M(match,);
int s,m,n,h,w;
scanf("%d%d%d%d%d",&s,&m,&n,&h,&w);
getchar();
for(int i=; i<s; i++)
{
char map_[m+][n+];
memset(zimu,false,sizeof(zimu));
for(int j=; j<m; j++)
gets(map_[j]);
for(int j=; j<m; j++)
for(int k=; k<n; k++)
if(map_[j][k]!='') zimu[map_[j][k]-'A']=true;
for(int j=; j<; j++)
{
int cnt=;
if(zimu[j])
{
char map_1[m+][n+];
for(int k=; k<m; k++)
for(int l=; l<n; l++)
if(map_[k][l]=='A'+j) map_1[k][l]='';
else map_1[k][l]=map_[k][l];
M(vis,);
for(int k=; k+h-<m; k++)
{
for(int l=; l+w-<n; l++)
{
if(map_1[k][l]==''&&!vis[k][l]&&k+h-<m&&l+w-<n)
{
bool ok=true;
for(int p=; p<h; p++)
{
for(int q=; q<w; q++)
{
if(map_1[k+p][l+q]!=''&&!vis[k+p][l+q])
{
ok=false;
}
}
}
if(ok) cnt=;
}
}
}
}
match[i+][j+]=cnt;
if(j+==)
{
M(vis,);
bool ok=true;
cnt=;
for(int k=; k+h-<m; k++)
{
for(int l=; l+w-<n; l++)
{
ok=true;
if(map_[k][l]==''&&!vis[k][l])
{
for(int p=; p<h; p++)
{
for(int q=; q<w; q++)
{
if(map_[k+p][l+q]!=''&&!vis[k+p][l+q])
{
ok=false;
}
}
}
if(ok) cnt=;
}
}
}
if(cnt) jump[i+]=true;
}
}
}
int ans=;
for(int i=; i<=s; i++)
{
M(visy,);
if(jump[i]) ans++;
else if(find_(i)) ans++;
}
printf("%d\n",ans);
}
return ;
}
/* 2
3 4 3 3 2
A0B
000
0A0
00B
AA0
00B
0B0
000
A0A
000
B00
B00
3 4 3 3 2
A0B
000
0A0
00B
AA0
00B
0B0
000
A0A
000
0B0
B00 */