详见进阶指南

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 1500
char mp[N][N];
int G[N][N],vis[N],match[N],n,m; bool dfs(int x){
for(int i=;i<=n;i++)
if(!vis[i] && G[x][i]){
vis[i]=;
if(!match[i] || dfs(match[i])){
match[i]=x;return ;
}
}
return ;
}
int work(){
int res=;
memset(match,,sizeof match);
for(int i=;i<=n;i++){
memset(vis,,sizeof vis);
if(dfs(i))res++;
}
return res;
} int cnt1,cnt2,id1[N][N],id2[N][N];//每个点对应的块序号
int main(){
for(int i=;i<=;i++)
for(int j=;j<=;j++)
mp[i][j]='.';
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("\n%c",&mp[i][j]);//这样很好用 //标记联通块
cnt1=,cnt2=;
memset(id1,,sizeof id1);
memset(id2,,sizeof id2);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(mp[i][j]=='*'){
if(mp[i][j-]==mp[i][j])
id1[i][j]=id1[i][j-];
else id1[i][j]=++cnt1;
if(mp[i-][j]==mp[i][j])
id2[i][j]=id2[i-][j];
else id2[i][j]=++cnt2;
} //建图
memset(G,,sizeof G);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(mp[i][j]=='*')
G[id1[i][j]][id2[i][j]]=;
n=max(cnt1,cnt2);
cout<<work()<<endl;
}
}

最新文章

  1. freemarker页面中文乱码
  2. CryptographicException异常处理方法
  3. Java程序员的日常 —— Java类加载中的顺序
  4. CentOS7安装mysql5
  5. java1.7集合源码阅读: Vector
  6. Heritrix源码分析(一) 包介绍(转)
  7. WCF学习系列二_使用IIS发布WCF服务
  8. IOS准备
  9. Masstransit开发基于消息传递的分布式应用
  10. Android 不通过USB数据线调试的方法
  11. 【BZOJ3450】【Tyvj1952】Easy 可能DP
  12. 初探LVS NAT与DR
  13. EF 6.x、EF Core实现dynamic动态查询和EF Core实现多个上下文实例池你了解多少?
  14. 最短Hamilton路径【状压DP】
  15. 下拉列表模仿placeholder效果
  16. ASP.NET Identity 三(转载)
  17. .NET Core2.0 使用EF做数据操作
  18. 用SLF4j/Logback打印日志-2
  19. 记自己的第一个完整的java web项目
  20. python学习笔记二:if语句及循环语句,断点,模块,pyc

热门文章

  1. C++之赋值、比较、逻辑运算符
  2. docker使用gitlab持续集成(1)
  3. 2019牛客暑期多校训练营(第八场) E 线段树+可撤销并查集
  4. JAVA数据结构之二叉树
  5. CSIC_716_20191102【input、数据类型概述、运算符】
  6. css---盒模型新增样式
  7. 利用VS 性能探查器 解决代码性能不高问题
  8. Delphi 窗口置顶的方法
  9. mysql中的字符串截取和替换
  10. JS 拷贝传值和引用传值