在一个 n×m 的方格地图上，某些方格上放置着炸弹。手动引爆一个炸弹以后，炸弹会把炸弹所在的行和列上的所有炸弹引爆，被引爆的炸弹又能引爆其他炸弹，这样连锁下去。 现在为了引爆地图上的所有炸弹，需要手动引爆其中一些炸弹，为了把危险程度降到最低，请算出最少手动引爆多少个炸弹可以把地图上的所有炸弹引爆。
输入格式 第一行输两个整数 n,mn,mn,m，用空格隔开。 接下来 nnn 行，每行输入一个长度为 mmm 的字符串，表示地图信息。0表示没有炸弹，1表示炸弹。 数据约定： 对于 60``% 的数据：1≤n,m≤1001 \le n, m \le 1001≤n,m≤100； 对于 10000% 的数据：1≤n,m≤1000 1 \le n, m \le 10001≤n,m≤1000； 数据量比较大，不建议用cin输入。
输出格式 输出一个整数，表示最少需要手动引爆的炸弹数。
样例输入 5 5 00010 00010 01001 10001 01000
样例输出 2
队里大佬要去打蓝桥杯了，最近疯狂在群里发计蒜客蓝桥杯模拟赛的题 昨天说写一道DFS看谁快 我改了三四版一直超时 直接写显然超时 存炸弹横纵坐标加爆炸与否也超时 然后标记了行列终于过了 然后大佬用的BFS也过了 过了以后说看题解是并查集emmm’ 反正我们现在怀疑数据7是一百万个炸弹哈哈哈 算了不说了，上代码. 应该还挺容易理解的我就偷懒不写注释了
时间13ms内存1344kB #include <cstdio> #include <iostream> #include <cstring> char map[1005][1005]; int m, n, bom, ans; int x[1005], y[1005]; void dfs(int h, int k) { map[h][k]='0'; if (x[h] == 0) { x[h] = 1; for (int i = 0; i < m; i++) { if(map[h][i] == '1') dfs(h, i); } } if (y[k] == 0) { y[k] = 1; for (int i = 0; i < n; i++) { if(map[i][k] == '1') dfs(i, k); } } } int main(int argc, char const *argv[]) { while (~scanf("%d %d", &n, &m)) { bom = 0, ans = 0; memset(map, 0, sizeof(map)); memset(x, 0, sizeof(x)); memset(y, 0, sizeof(y)); for (int i = 0; i < n; i++) { scanf("%s", &map[i]); } for(int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if(map[i][j] == '1') { ans++; dfs(i, j); } } } printf("%d\n", ans); } return 0; }