#include #include #include using namespace std; #define Nmax 512 int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; bool ok; int N, M; char G[Nmax][Nmax]; int W[Nmax][Nmax], minlvl[Nmax][Nmax]; int nr, nrc, ox, oy; void critice(int nx, int ny, int lvl, int px, int py) { W[nx][ny] = lvl; minlvl[nx][ny] = lvl + 1; for (int i=0; i<4; ++i) { if (!W[nx+dx[i]][ny+dy[i]] && G[nx+dx[i]][ny+dy[i]] == '1') critice(nx+dx[i], ny+dy[i], lvl+1, nx, ny); } for (int i=0; i<4; ++i) { if (G[nx+dx[i]][ny+dy[i]] == '1' && (nx+dx[i] != px || ny+dy[i] != py)) minlvl[nx][ny] = min(minlvl[nx][ny], min(minlvl[nx+dx[i]][ny+dy[i]], W[nx+dx[i]][ny+dy[i]])); } if (minlvl[nx][ny] > lvl) ++nrc; //printf("(%d %d) %d %d\n", nx, ny, lvl, minlvl[nx][ny]); } int main() { // freopen("test.in", "r", stdin); scanf("%d %d\n", &N, &M); for (int i=1; i<=N; ++i) fgets(G[i]+1, 512, stdin); // critice(N, M, 1, 0, 0); // if (ok) --nrc; for (int i=1; i<=N; ++i) for (int j=1; j<=M; ++j) if (G[i][j] == '1') { ++nr; if (!W[i][j]) { critice(i, j, 1, 0, 0); } } printf("%d\n", nr-nrc); return 0; }