ZOJ 1654 Place the Robots
2024-09-08 02:24:59
题目大意:
在空地上放置尽可能多机器人,机器人朝上下左右4个方向发射子弹,子弹能穿过草地,但不能穿过墙,
两个机器人之间的子弹要保证互不干扰,求所能放置的机器人的最大个数
每个机器人所在的位置确定了,那么对应的横向和竖向子弹能到达的空地就全部被覆盖了
我们将横向所能连接在一块的空地区域标上同一个标号
比如o*o#o , 就可标号为10102因为1,3空地中间的草地不影响子弹的穿越
同理,我们将竖向的所能连接在一块的空地区域标上同一个标号
那么就可以建立一个横向到达竖向的二部图匹配
每次成功匹配一对,就相当于在这横竖交叉处放了一个炮台
这就转化成了最大匹配数
#include <cstdio>
#include <cstring> using namespace std;
const int N = ; char str[N][N];
int n , m , xs[N][N] , ys[N][N] , idx , idy;//idx记录以行为轴的最大标号,idy则表示以列为轴的最大标号
int cx[N*N] , cy[N*N] , visy[N*N];
bool g[N*N][N*N];//int是4个字节,用int会MLE,bool一个字节 int dfs(int u)
{
for(int v = ; v<=idy ; v++){
if(g[u][v] && !visy[v]){
visy[v] = ;
if(cy[v] == - || dfs(cy[v])){
cx[u] = v;
cy[v] = u;
return ;
}
}
}
return ;
} int MaxMatch()
{
memset(cx , - , sizeof(cx));
memset(cy , - , sizeof(cy));
int ans = ;
for(int i= ; i<=idx ; i++){
if(cx[i] == -){
memset(visy , , sizeof(visy));
ans += dfs(i);
}
}
return ans;
} int main()
{
// freopen("a.in" , "r" , stdin);
int T , cas = ;
scanf("%d" , &T);
while(T--)
{
scanf("%d%d" , &n , &m);
for(int i = ; i<n ; i++)
scanf("%s" , str[i]); //给每行炮台所能触及的位置编为相同号
int id = , flag = ;
for(int i= ; i<n ; i++){
if(flag) flag = , id++;
for(int j = ; j < m ; j++){
if(str[i][j] == 'o')
xs[i][j] = id , idx = id , flag = ;
else if(str[i][j] == '#')
flag = , id++;
}
} //给每列炮台所能触及的位置编为相同号
id = , flag = ;
for(int i= ; i<m ; i++){
if(flag) flag = , id++;
for(int j = ; j < n ; j++){
if(str[j][i] == 'o')
ys[j][i] = id , idy = id , flag = ;
else if(str[j][i] == '#')
flag = , id++;
}
} //构造二部图
memset(g , , sizeof(g));
for(int i = ; i<n ; i++)
for(int j = ; j<m ; j++){
if(str[i][j] == 'o')
g[xs[i][j]][ys[i][j]] = true;
}
printf("Case :%d\n%d\n" , ++cas , MaxMatch());
}
return ;
}
最新文章
- hihoCoder#1094
- xcode 制作静态库.a文件 详解
- DOM(六)事件类型
- POJ 1988
- iOS-assign、copy 、retain等关键字的含义
- zabbix web场景模拟监控配置
- Linux磁盘分区实战案例
- poj1036-dp
- 深入tornado中的协程
- pip使用国内源
- nginx 重定向 说明
- Python基础4 迭代器、装饰器、软件开发规范
- Unity3D学习笔记——Android远程真机调试(Unity Remote)
- InsertSql
- .NET中使用Rabbit MQ
- eclipse无法启动
- 通过vertical-align属性实现“竖向居中”显示
- [agc011F]Train Service Planning-[线段树优化dp+神秘思考题]
- JS框架的实现
- No module named &#39;_Sqlite3&#39; 解决方法
热门文章
- 构造 Codeforces Round #107 (Div. 2) B. Phone Numbers
- 题解报告:poj 1321 棋盘问题(dfs)
- 数据传递-------ajaxJson------spring3mvc中使用ajax传json中文乱码解决
- 389 Find the Difference 找不同
- 283 Move Zeroes 移动零
- 20 如何在C#中存一批数据,数组
- CF864D Make a Permutation!
- plc学习笔记
- socket相关函数
- linux nohup &; 简单使用