题目链接 https://nanti.jisuanke.com/t/A1139
在一个 n times mn×m 的方格地图上，某些方格上放置着炸弹。手动引爆一个炸弹以后，炸弹会把炸弹所在的行和列上的所有炸弹引爆，被引爆的炸弹又能引爆其他炸弹，这样连锁下去。
现在为了引爆地图上的所有炸弹，需要手动引爆其中一些炸弹，为了把危险程度降到最低，请算出最少手动引爆多少个炸弹可以把地图上的所有炸弹引爆。
输入格式
第一行输两个整数 n,mn,m，用空格隔开。
接下来 nn 行，每行输入一个长度为 mm 的字符串，表示地图信息。0表示没有炸弹，1表示炸弹。
数据约定：
对于 60%60% 的数据：1 le n, m le 1001≤n,m≤100；
对于 100%100% 的数据：1 le n, m le 10001≤n,m≤1000；
数据量比较大，不建议用cin输入。
输出格式
输出一个整数，表示最少需要手动引爆的炸弹数。
样例输入
5 5 00010 00010 01001 10001 01000
样例输出
2
思路：我开始认为是简单的bfs，便开始用bfs实现，但是很明显在第8个样例时卡住了我想如果是1000*1000个点都是1就要重复遍历1e9这样就会超时，所以对于每一次遍历过的边标记一次下一次就不用再次标记
代码如下
#include<bits/stdc++.h> using namespace std; int a[1005][1005]; int m,n,ans=0; int bow[1005]; int col[1005]; int bfs(int i,int j) { a[i][j]=0; if(!bow[j]) { bow[j]=1; for(int k=1;k<=n;k++) { if(a[k][j]==1) bfs(k,j); } } if(!col[i]) { col[i]=1; for(int l=1;l<=m;l++) { if(a[i][l]==1) bfs(i,l); } } } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%1d",&a[i][j]); } } for(int i=1;i<=n;i++ ) { for(int j=1;j<=m;j++) { if(a[i][j]==1) { bfs(i,j); ans++; } } } printf("%d",ans); }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
