HDU1198水管并查集Farm Irrigation
Farm Irrigation
Figure 1
Benny has a map of his farm, which is an array of marks denoting the distribution of water pipes over the whole farm. For example, if he has a map
ADC
FJK
IHE
then the water pipes are distributed like
Figure 2
Several wellsprings are found in the center of some squares, so water can flow along the pipes from one square to another. If water flow crosses one square, the whole farm land in this square is irrigated and will have a good harvest in autumn.
Now Benny wants to know at least how many wellsprings should be found to have the whole farm land irrigated. Can you help him?
Note: In the above example, at least 3 wellsprings are needed, as those red points in Figure 2 show.
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
char a[55][55];
int pd[2505];
struct node
{
int l;
int r;
int u;
int d;
int num;
}que[55][55];
int get(int x)
{
if(pd[x]!=x)
pd[x]=get(pd[x]);
return pd[x];
}
void find(int x,int y)
{
pd[get(y)]=get(x);
}
int main()
{
int m,n;
while(scanf("%d%d",&m,&n)!=EOF)
{
if(m==-1&&n==-1)
break;
if(m==1&&n==1)
{
printf("1\n");
continue;
}
memset(pd,0,sizeof(pd));
memset(a,0,sizeof(a));
int N=n*m;
for(int i1=1;i1<=N;i1++)
pd[i1]=i1;
getchar();
for(int i2=0;i2<m;i2++)
{
for(int j2=0;j2<n;j2++)
scanf("%c",&a[i2][j2]);
getchar();
}
int h=1;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
if(a[i][j]=='A') {que[i][j].l=1;que[i][j].r=0;que[i][j].u=1;que[i][j].d=0;}
else if(a[i][j]=='B') {que[i][j].l=0;que[i][j].r=1;que[i][j].u=1;que[i][j].d=0;}
else if(a[i][j]=='C') {que[i][j].l=1;que[i][j].r=0;que[i][j].u=0;que[i][j].d=1;}
else if(a[i][j]=='D') {que[i][j].l=0;que[i][j].r=1;que[i][j].u=0;que[i][j].d=1;}
else if(a[i][j]=='E') {que[i][j].l=0;que[i][j].r=0;que[i][j].u=1;que[i][j].d=1;}
else if(a[i][j]=='F') {que[i][j].l=1;que[i][j].r=1;que[i][j].u=0;que[i][j].d=0;}
else if(a[i][j]=='G') {que[i][j].l=1;que[i][j].r=1;que[i][j].u=1;que[i][j].d=0;}
else if(a[i][j]=='H') {que[i][j].l=1;que[i][j].r=0;que[i][j].u=1;que[i][j].d=1;}
else if(a[i][j]=='I') {que[i][j].l=1;que[i][j].r=1;que[i][j].u=0;que[i][j].d=1;}
else if(a[i][j]=='J') {que[i][j].l=0;que[i][j].r=1;que[i][j].u=1;que[i][j].d=1;}
else {que[i][j].l=1;que[i][j].r=1;que[i][j].u=1;que[i][j].d=1;}
que[i][j].num=h;
h++;
}
for(int i3=0;i3<m;i3++)
for(int j3=0;j3<n;j3++)
{
if(j3<n-1)
{
if(que[i3][j3].r==1&&que[i3][j3+1].l==1)
find(que[i3][j3].num,que[i3][j3+1].num);
}
if(i3<m-1)
{
if(que[i3][j3].d==1&&que[i3+1][j3].u==1)
find(que[i3][j3].num,que[i3+1][j3].num);
}
}
int sum=0;
for(int i4=1;i4<=N;i4++)
{
if(pd[i4]==i4)
sum++;
}
printf("%d\n",sum);
}
return 0;
}
最新文章
- redis-cli -h xxxxx -p xxxx monitor 监控host为xxxx,端口为xxx,redis连接及读写操作
- BZOJ 2763 分层图最短路
- linux 磁盘管理以及维护
- bzoj1975
- java nio 快速read大文件
- openstack 源码分析
- Linux 多线程通信
- Nginx Rewrite规则记录
- url语法
- ASP从HTML标签中提取中文
- Java SE之正则表达式四:获取
- JavaScript原型与闭包相关
- 322. Coin Change选取最少的硬币凑整-背包问题变形
- JAVA记录-生成jar包方法
- Python实现Linux命令xxd -i功能
- #pragma alloc_text
- SVG 动画(animate、animateTransform、animateMotion)
- [buaa-SE-2017]个人作业-Week1
- linux网口驱动实现(待续)
- 无法启动mysql服务 错误1067:进程意外中止
热门文章
- jQuery使用之(二)设置元素的样式
- angular实例教程(用来熟悉指令和过滤器的编写)
- 调研Android平台开发环境的发展演变
- Ibatis学习总结1--ibatis简介和SQL Maps
- Java基础-内部类
- JEECMS插件开发
- Bringing up interface eth0: Error:Connection activation failed:Device not managed by NetworkManager
- Java输入、输入、IO流 类层次关系梳理
- 转-Android中自动连接到指定SSID的Wi-Fi
- C#获取本机的MAC地址