1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn = 1000 + 10;
 5 const int maxm = 1000 + 10;
 6 int n,m;
 7 bool maze[maxn][maxm];
 8 bool r[maxn], c[maxm];
 9 char s[maxm];
10 int dn[maxn][maxm], ds[maxn][maxm], dw[maxn][maxm], de[maxn][maxm];
11 
12 void init()
13 {
14     //memset(dn, -1, sizeof(dn));
15     //memset(ds, -1, sizeof(ds));
16     //memset(dw, -1, sizeof(dw));
17     //memset(de, -1, sizeof(de));
18     for(int j = 0;j < m;j++)
19     {
20         int flagn = -1;
21         for(int i = 0;i < n;i++)
22         {
23             dn[i][j] = flagn;
24             if(maze[i][j] == 1)  flagn = i;
25         }
26     }
27 
28     for(int j = 0;j < m;j++)
29     {
30         int flags = -1;
31         for(int i = n-1;i >= 0;i--)
32         {
33             ds[i][j] = flags;
34             if(maze[i][j] == 1)  flags = i;
35         }
36     }
37 
38     for(int i = 0;i < n;i++)
39     {
40         int flagw = -1;
41         for(int j = 0;j < m;j++)
42         {
43             dw[i][j] = flagw;
44             if(maze[i][j] == 1)  flagw = j;
45         }
46     }
47 
48     for(int i = 0;i < n;i++)
49     {
50         int flage = -1;
51         for(int j = m - 1;j >= 0;j--)
52         {
53             de[i][j] = flage;
54             if(maze[i][j] == 1)  flage = j;
55         }
56     }
57 }
58 
59 int cnt = 0;
60 void dfs(int i, int j)
61 {
62     //printf("%d %d\n", i, j);
63     maze[i][j] = 0;
64     r[i] = c[j] = true;
65 
66     if(dn[i][j] != -1 && maze[dn[i][j]][j] == 1)  dfs(dn[i][j], j);
67     if(ds[i][j] != -1 && maze[ds[i][j]][j] == 1)  dfs(ds[i][j], j);
68     if(dw[i][j] != -1 && maze[i][dw[i][j]] == 1)  dfs(i, dw[i][j]);
69     if(de[i][j] != -1 && maze[i][de[i][j]] == 1)  dfs(i, de[i][j]);
70 
71 }
72 
73 
74 int main()
75 {
76     scanf("%d%d", &n,&m);
77     for(int i = 0;i < n;i++)
78     {
79         scanf("%s", s);
80         for(int j = 0;j < m;j++)  maze[i][j] = s[j] - ‘0‘;
81     }
82 
83     init();
84 
85     int ans = 0;
86     for(int i = 0;i <n;i++)
87         for(int j = 0;j < m;j++)
88         {
89             if(maze[i][j] == 1 && (!r[i]) && (!c[j]))  //出现过的行和列肯定不可能再存在“未爆炸”的炸弹
90             {
91                 dfs(i, j);
92                 ans++;
93             }
94         }
95     printf("%d\n", ans);
96 
97     return 0;
98 }