题目:
在一个 n×mn \times mn×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
这个题我用深搜写的,题意是1是炸弹,现在要引爆炸弹,炸弹所在的行和列都会引爆,为了节省时间,可以把炸完的炸弹所在的行和列标记,然后去寻找该炸弹所在行或者列的其他炸弹。
程序代码:
#include<stdio.h> #include<string.h> char s[1100][1100]; int a[1100][1100]; int c[1010],b[1010]; int n,m; void dfs(int x,int y) { int i,j,k; a[x][y]=0; if(b[x]==0)//标记行 { b[x]=1; for(i=0;i<m;i++) { if(a[x][i]==1) dfs(x,i); } } if(c[y]==0)//标记列 { c[y]=1; for(j=0;j<n;j++) { if(a[j][y]==1) dfs(j,y); } } } int main() { int i,k,j,sum; while(scanf("%d%d",&n,&m)!=EOF) { sum=0; memset(c,0,sizeof(c)); memset(b,0,sizeof(b)); for(i=0;i<n;i++) scanf("%s",s[i]); for(i=0;i<n;i++) for(j=0;j<m;j++) a[i][j]=s[i][j]-'0'; for(i=0;i<n;i++) for(j=0;j<m;j++) { if(a[i][j]==1&&b[i]==0&&c[j]==0) { dfs(i,j); sum++; } } printf("%d\n",sum); } return 0; }