首页 > 代码库 > 蓝桥杯模拟赛-引爆炸弹-DFS+并查集
蓝桥杯模拟赛-引爆炸弹-DFS+并查集
今天整理电脑,翻出来了很久以前大佬给的题,贴一下。
引爆炸弹
1000ms
在一个 n×m的方格地图上,某些方格上放置着炸弹。手动引爆一个炸弹以后,炸弹会把炸弹所在的行和列上的所有炸弹引爆,被引爆的炸弹又能引爆其他炸弹,这样连锁下去。
现在为了引爆地图上的所有炸弹,需要手动引爆其中一些炸弹,为了把危险程度降到最低,请算出最少手动引爆多少个炸弹可以把地图上的所有炸弹引爆。
输入格式
第一行输两个整数 n,mn,mn,m,用空格隔开。
接下来 nnn 行,每行输入一个长度为 mmm 的字符串,表示地图信息。0
表示没有炸弹,1
表示炸弹。
数据约定:
对于 60%60\%60% 的数据:1≤n,m≤1001 \le n, m \le 1001≤n,m≤100;
对于 100%100\%100% 的数据:1≤n,m≤1000 1 \le n, m \le 10001≤n,m≤1000;
数据量比较大,不建议用cin
输入。
输出格式
输出一个整数,表示最少需要手动引爆的炸弹数。
样例输入
5 5 00010 00010 01001 10001 01000
样例输出
2
样例的方法如下:先引手动引爆一个炸弹,红色的手动引爆,绿色的是间接引爆。
然后再手动引爆一个炸弹:
因此最少需要手动引爆两枚炸弹。
贴大佬代码:
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<vector> #include<cstdlib> #include<string> #define eps 0.000000001 typedef long long ll; typedef unsigned long long LL; using namespace std; const int N=1000+10; int m,n; int t; int vis[N]; struct node{ int x,y; }a[N]; int parent[N]; void init(){ memset(vis,0,sizeof(vis)); for(int i=0;i<=N;i++)parent[i]=i; } int find(int x){ int r=x; while(r!=parent[r])r=parent[r]; int i=x; int j; while(parent[i]!=r){ j=parent[i]; parent[i]=r; i=j; } return r; } void Union(int x,int y){ x=find(x); y=find(y); if(x!=y)parent[x]=y; } void DFS(int x){ vis[x]=1; for(int i=0;i<t;i++){ if(vis[i]==0&&(a[i].x==a[x].x||a[i].y==a[x].y)){ Union(i,x);DFS(i); } } } int main(){ char c; init(); scanf("%d%d",&m,&n); getchar(); t=0; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++){ cin>>c; if(c==‘1‘){a[t].x=i;a[t].y=j;t++;} } for(int i=0;i<t;i++)DFS(i); int ans=0; for(int i=0;i<t;i++){ if(parent[i]==i)ans++; } cout<<ans<<endl; }
蓝桥杯模拟赛-引爆炸弹-DFS+并查集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。