hdu5652 India and China Origins(并查集)

时间:2021-09-08 12:06:03

India and China Origins

 Accepts: 49
 Submissions: 426
 Time Limit: 2000/2000 MS (Java/Others)
 Memory Limit: 65536/65536 K (Java/Others)
问题描述
很久以前,中国和印度之间并没有喜马拉雅山相隔,两国的文化交流很频繁。随着喜马拉雅山海拔逐渐增加,两个地区的交流也越来越少,最终没有了来往。

hdu5652 India and China Origins(并查集)

假设当时的地形和我画的一样,蓝色部分代表海洋,而且当时人们还没有发明轮船。黄色部分代表沙漠,而且沙漠上经常有野鬼散步,所以人们不敢到沙漠中行走。黑色的格子表示山峰,这些山峰都无比高大,所以人无法穿过。白色格子代表平原,人可以在平原上*行走。人每次可以向相邻的四个格子走动。

此外,我们的考古学家发现还有一些山峰会逐渐形成,通过研究发现,位置在 (x, y)(x,y) (保证该位置之前没有山峰)的地方在 ii 年后出现了山峰。现在给你若干个位置出现山峰的时间,你可以计算出中国和印度之间的联系最早被彻底切断的时间吗?
输入描述
多组测试数据, 第一行为组数T(T\leq 10)T(T≤10)。每组测试数据第一行包含两个数 N, M (1 \leq N, M \leq 500)N,M(1≤N,M≤500), 表示地图的大小。接下来 NN 行长度为 MM 的 0101 字符串。00代表白色格子,11 代表山峰。接下来有 Q(1\leq Q \leq N\times M)Q(1≤Q≤N×M) 行,第 i(1\leq i \leq Q)i(1≤i≤Q) 两个整数 (x,y),0 \leq x < N, 0 \leq y < M(x,y),0≤x<N,0≤y<M 表示在第 ii 年 (x,y)(x,y) 出现了一座山峰。
输出描述
对于每组测试数据,输出一个数, 表示两国最早失联的时间。如果最终两国之间还有联系则输出 -1。
输入样例
1
4 6
011010
000010
100001
001000
7
0 3
1 5
1 3
0 0
1 2
2 4
2 1
输出样例
4
Hint

hdu5652 India and China Origins(并查集)

从上图可以看到,两国在第四年彻底失去了联系。
/*
hdu5652 India and China Origins(并查集) 给你一个棋盘形状的东东,上面1代表无法越过的山峰,0代表可以通过的平原.
而且在接下来q次会出现一些山峰,问多少次后棋盘上下不连通
如果一直联通则输出-1 开始想到了并查集但是实现起来有点问题,每次插入后都要把最左边一列判断
一下,看他们的父亲是否是棋盘的最右端.感觉并不够简便
然后参考了下大神们的代码,发现可以在合并的时候记录下这个联通量最左边
和最右边的位置,这样每次合并时只需要判断max-min是否等于棋盘的宽度就
好了
果然自己太死板了TAT hhh-2016-03-27 12:42:45
*/ #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define lson (i<<1)
#define rson ((i<<1)|1)
typedef long long ll;
const int maxn = 505 ;
int from = 500*500;
int to = 500*500+1;
int n,m;
int dir[9][2] = {{1,1},{1,0},{0,1},{1,-1},{0,-1},{-1,1},{-1,-1},{-1,0}};
char str[maxn];
int far[maxn*maxn];
int tmap[maxn][maxn];
int l[maxn*maxn],r[maxn*maxn]; int fin(int x)
{
return x == far[x]? x : far[x] = fin(far[x]);
} bool unio(int a,int b)
{
int ta = fin(a);
int tb = fin(b);
if(ta != tb)
{
far[ta] = tb;
l[tb] = min(l[ta],l[tb]);
r[tb] = max(r[ta],r[tb]);
if(r[tb] - l[tb] == m-1)
return 1;
}
return 0;
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i = 0; i < n; i++)
{
scanf("%s",str);
for(int j = 0; j < m; j++)
{
tmap[i][j] = str[j]-'0';
far[i*m+j] = i*m+j;
}
} for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
//if(tmap[i][j])
{
l[i*m+j] = j;
r[i*m+j] = j;
}
}
int flag =0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if(tmap[i][j])
{
for(int k = 0; k < 8; k++)
{
int tx = i + dir[k][0];
int ty = j + dir[k][1];
if(tx < 0 || tx >= n || ty < 0 || ty >= m || !tmap[tx][ty])
continue;
if(unio(i*m+j,tx*m+ty))
flag = 1;
} }
}
}
if(flag)
printf("0\n");
int q;
scanf("%d",&q);
for(int i = 0; i < q; i++)
{
int x,y;
scanf("%d%d",&x,&y);
tmap[x][y] = 1;
if(flag)
continue;
for(int k = 0; k < 8; k++)
{
int tx = x + dir[k][0];
int ty = y + dir[k][1];
if(tx < 0 || tx >= n || ty < 0 || ty >= m || !tmap[tx][ty])
continue;
if(unio(x*m+y,tx*m+ty))
{
flag = 1;
printf("%d\n",i+1);
}
}
}
if(!flag)
printf("-1\n");
}
return 0 ;
}

  

														
		

hdu5652 India and China Origins(并查集)的更多相关文章

  1. hdu 5652 India and China Origins 并查集&plus;二分

    India and China Origins Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/ ...

  2. hdu 5652 India and China Origins 并查集

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5652 题目大意:n*m的矩阵上,0为平原,1为山.q个询问,第i个询问给定坐标xi,yi,表示i年后这 ...

  3. hdu 5652 India and China Origins 并查集&plus;逆序

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5652 题意:一张n*m个格子的点,0表示可走,1表示堵塞.每个节点都是四方向走.开始输入初始状态方格, ...

  4. hdu-5652 India and China Origins&lpar;二分&plus;bfs判断连通&rpar;

    题目链接: India and China Origins Time Limit: 2000/2000 MS (Java/Others)     Memory Limit: 65536/65536 K ...

  5. hdu5652&colon;India and China Origins(并查集)

    倒序操作用并查集判断是否连通,新技能get√(其实以前就会了 这题细节很多...搞得整个程序都是调试输出,几度看不下去想要重写 并查集到现在大概掌握了两个基本用途:判断是否连通 / 路径压缩(上一篇b ...

  6. 并查集&lpar;逆序处理&rpar;:HDU 5652 India and China Origins

    India and China Origins Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/ ...

  7. HDU 5652 India and China Origins(并查集)

    India and China Origins Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/ ...

  8. HDU 5652 India and China Origins 二分&plus;并查集

    India and China Origins 题目连接: http://acm.hdu.edu.cn/showproblem.php?pid=5652 Description A long time ...

  9. HDU 5652 India and China Origins(经典并查集)

    特别经典的一个题,还有一种方法就是二分+bfs 题意:空间内n*m个点,每个点是0或者1,0代表此点可以走,1代表不能走.接着经过q年,每年一个坐标表示此点不能走.问哪年开始图上不能出现最上边不能到达 ...

随机推荐

  1. Bugtags 测试平台(支持ios、android)

    官网:https://bugtags.com/ 注意:小米手机 授权 打开漂浮窗 App 集成 Bugtags SDK 后,测试人员就可直接在 App 里所见即所得的提交 Bug; SDK 会自动截屏 ...

  2. Ruby-递归和尾递归

    递归和迭代的区别 递归: 1)递归就是在过程或函数里面调用自身; 2)在使用递归时,必须有一个明确的递归结束条件,称为递归出口. 迭代: 利用变量的原值推算出变量的一个新值.如果递归是自己调用自己的话 ...

  3. 从tomcat启动到springIoC容器初始化(编辑中)

    tomcat的启动一般是从startup.bat/startup.sh开始,然后启动catalina.bat/catalina.sh,然后启动bootstrap.jar包 那么它们启动的时候都做了哪些 ...

  4. Lua与C的交互

    Lua 与 C 的交互 Lua是一个嵌入式的语言,它不仅可以是一个独立运行的程序,也可以是一个用来嵌入其它应用的程序库. C API是一个C代码与Lua进行交互的函数集,它由以下几部分构成: 1.  ...

  5. 在Linux下部署activemq

    今天的任务就是在一台新的服务器上继续部署activemq.其实都蛮简单的.首先先下载包:115U盘下载 2 上传到linux下的某个文件夹下.解压缩 tar -zxvf apache-activemq ...

  6. VC中获取窗体句柄的各种方法

    AfxGetMainWnd AfxGetMainWnd获取自身窗体句柄 HWND hWnd = AfxGetMainWnd()->m_hWnd; GetTopWindow 函数功能:该函数检查与 ...

  7. (IOS)CoreLocation 和 MapKit 的应用

    CoreLocation是控制GPS硬件获取地理坐标信息的系统类库,而MapKit是系统地图的工具包,将两者结合使用可以实现不同的地图功能. 1.CoreLocation 在CoreLocation中 ...

  8. &lbrack;转&rsqb;PostgreSQL事务处理机制

    原文链接:http://blog.chinaunix.net/uid-20726500-id-4040024.html 事务的实现原理可以解读为DBMS采取何种技术确保事务的ACID特性.Postgr ...

  9. Kafka Frequently Asked Questions

    This is intended to be an easy to understand FAQ on the topic of Kafka. One part is for beginners, o ...

  10. Python IDLE 代码高亮主题

    Python IDLE 代码高亮主题 使用方法: 打开C盘我的 C:\Documents and Settings\你的用户名.idlerc文件夹 里面会有一个 config-highlight.cf ...