#include #include int n, m; char c[502][502]; short int seen[250001]; unsigned long int szint[250001], apa[250001], graf[250001][5]; unsigned long int l = 0; void Init() { int i, j; for (i = 1; i <= n*m; i++) { seen[i] = 0; for (j = 0; j < 5; j++) graf[i][j] = 0; } for (i = 1; i <= n+1; i++) for (j = 1; j <= m+1; j++) c[i][j] = '0'; } int ElvagoEl(unsigned long int v, unsigned long int sz) { unsigned long int rfminvm = 1000000, i, uminvm; seen[v] = 1; szint[v] = sz; for (i = 1; i <= graf[v][0]; i++) { if ((graf[v][i]) && (!seen[graf[v][i]])) { apa[graf[v][i]] = v; uminvm = ElvagoEl(graf[v][i], sz+1); if (uminvm <= sz) if (uminvm < rfminvm) rfminvm = uminvm; } else if ((graf[v][i]) && (seen[i] == 1)) { if (szint[graf[v][i]] < sz-1) if (szint[graf[v][i]] < rfminvm) rfminvm = szint[graf[v][i]]; } } seen[v] = 2; if (rfminvm != 1000000) l++; return rfminvm; } int main() { int i, j; unsigned long int k; scanf("%d%d", &n, &m); Init(); gets(c[0]); for (i = 0; i < n; i++) for (j = 0; j < m+1; j++) scanf("%c", &c[i][j]); for (i = 0; i < n; i++) for (j = 0; j < m; j++) if (c[i][j] == '1') { if (c[i+1][j] == '1') { graf[i*m+j+1][0]++; graf[i*m+j+1][graf[i*m+j+1][0]] = (i+1)*m+j+1; graf[(i+1)*m+j+1][0]++; graf[(i+1)*m+j+1][graf[(i+1)*m+j+1][0]] = i*m+j+1; } if (c[i][j+1] == '1') { graf[i*m+j+1][0]++; graf[i*m+j+1][graf[i*m+j+1][0]] = i*m+j+2; graf[i*m+j+2][0]++; graf[i*m+j+2][graf[i*m+j+2][0]] = i*m+j+1; } } for (i = 0; i < n; i++) for (j = 0; j < m; j++) if (!seen[i*m+j+1]) k = ElvagoEl(i*m+j+1, 0); printf("%lu", l); return 0; }