（計蒜客藍橋杯模拟賽 五）程式設計：引爆炸彈

程式設計：引爆炸彈

時間限制	1000ms
記憶體限制	131072K

在一個 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

隊裡大佬要去打藍橋杯了，最近瘋狂在群裡發計蒜客藍橋杯模拟賽的題

昨天說寫一道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;
}