在一个 n × m n×mn×m 的方格地图上，某些方格上放置着炸弹。手动引爆一个炸弹以后，
炸弹会把炸弹所在的行和列上的所有炸弹引爆，被引爆的炸弹又能引爆其他炸弹，这样连锁下去。
现在为了引爆地图上的所有炸弹，需要手动引爆其中一些炸弹，为了把危险程度降到最低，请算出最少手动引爆多少个炸弹可以把地图上的所有炸弹引爆。
输入格式
第一行输两个整数 n , m 。n,m用空格隔开。
接下来 n 行，每行输入一个长度为 m 的字符串，表示地图信息。0表示没有炸弹，1表示炸弹。
数据约定：
对于 60 % 的数据：1 ≤ n , m ≤ 100 1≤n；
对于 100 % 的数据：1 ≤ n , m ≤ 1000 ；
输出格式
输出一个整数，表示最少需要手动引爆的炸弹数。
输入样例：
5 5 00010 00010 01001 10001 01000
输出样例：
2
#include <iostream> using namespace std; int n,m; char a[1005][1005]; bool vx[1005],vy[1005]; int number; void dfs(int x,int y){ //x行y列 a[x][y]='0'; if(!vx[x]){ //重复性剪枝 vx[x]=true; for(int i=0;i<m;i++){ if(a[x][i]=='1'){ dfs(x,i); } } } if(!vy[y]){ //重复性剪枝 vy[y]=true; for(int i=0;i<n;i++){ if(a[i][y]=='1'){ dfs(i,y); } } } } int main(){ cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>a[i][j]; } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i][j]=='1'){ number++; dfs(i,j); } } } cout<<number; return 0; }
