出原题,直接二分图匹配即可。

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i) vector <int> v[3005]; int n,m,map[55][55],mx,ans;
int le[55][55],ri[55][55],vis[3005],linker[3005];
char s[55]; bool dfs(int o)
{
for (int i=0;i<v[o].size();++i)
if (!vis[v[o][i]]){
vis[v[o][i]]=1;
if (!linker[v[o][i]]||dfs(linker[v[o][i]]))
{
linker[v[o][i]]=o;
return true;
}
}
return false;
} int main()
{
scanf("%d%d",&n,&m);
F(i,1,n)
{
scanf("%s",s+1);
F(j,1,m)
switch(s[j])
{
case '*': map[i][j]=1;break;
case '#': map[i][j]=-1;break;
case 'x': map[i][j]=0;break;
}
}
F(i,0,n+1) map[i][0]=map[i][m+1]=-1;
F(i,0,m+1) map[n+1][i]=map[0][i]=-1;
int cnt=0,con=1;
F(i,0,n) F(j,0,m)
if (map[i][j]!=-1) con=1,le[i][j]=cnt;
else{if (con) ++cnt,con=0;}
mx=cnt;cnt=0,con=1;
F(j,0,m) F(i,0,n)
if (map[i][j]!=-1) con=1,ri[i][j]=cnt;
else {if (con) ++cnt,con=0;}
F(i,1,n) F(j,1,m)
if (map[i][j]==1)
v[le[i][j]].push_back(ri[i][j]);
F(i,1,mx)
{
memset(vis,0,sizeof vis);
if (dfs(i)) ans++;
}
printf("%d\n",ans);
}

  

最新文章

  1. 在IDEA上跑eclipse开发的J2EE项目
  2. Matlab 语谱图(时频图)绘制与分析
  3. Cocoa的MVC架构分析 cocoa的mvc实现
  4. Rabbitmq init terminating in do boot 问题
  5. erlang程序优化点的总结(持续更新)
  6. spring jdbc 源码
  7. highcharts柱状图和饼图的数据填充
  8. MySQL优化三(InnoDB优化)
  9. 对接第三方平台JAVA接口问题推送和解决
  10. 团队作业4——第一次项目冲刺(Alpha版本)
  11. React Native之样式
  12. Eclipse install new software无反应
  13. Git是什么、Git的功能、为什么versioncontrol用Git、Git的常用命令、Git的优缺点
  14. Python——Redis相关知识
  15. js生成二维码 qrcode
  16. 淘宝Tengine 2.1.2 稳定版(nginx/1.6.2) Centos 6.5安装教程
  17. 文件编码检测.ZC
  18. Debug 单步执行命令step into/step out/step over的区别
  19. .netcore部署centos
  20. hdu4549矩阵快速幂+费马小定理

热门文章

  1. 【转】 iOS学习之NSBundle介绍和使用
  2. Java Marker Interface
  3. LibreOffice Writer Comment
  4. iOS小技巧–用runtime 解决UIButton 重复点击问题
  5. k8s基于canel的网络策略
  6. CentOS7安装配置VSFTP
  7. 【mac】【转发】Mac系统升级后,按大小写键没反应了,切换大小写的灯不亮了
  8. 22.Yii2.0框架多表关联一对一查询之hasOne
  9. leetcode-15-basic-string
  10. leetcode-6-basic