#include #include #include #include #include #include #include #include #include #include #include #include #include #define JUDGE1 using namespace std; vector MAT; int VIZ[501][501]; int N, M, cnt, pas; int dx[] = { -1, 0, 1, 0 }; int dy[] = { 0, 1, 0, -1 }; void dfs(int tox, int toy, int fromx = -1, int fromy = -1); void dfs2(int x, int y); int main() { #ifndef JUDGE freopen("input.txt", "r", stdin); #endif int i, j; cin >> N >> M; MAT.resize(N); for (i = 0; i < N; ++i) { cin >> MAT[i]; } pas = 1; for (i = 0; i < N; ++i) { for (j = 0; j < M; ++j) { if (MAT[i][j] == '1' && VIZ[i][j] == 0) { ++pas; dfs(i, j); } } } cout << cnt; #ifndef JUDGE while (1); #endif return 0; } void dfs(int tox, int toy, int fromx, int fromy) { int nx, ny, i = 0, ok1 = 0; VIZ[tox][toy] = pas; for (i = 0; i < 4; ++i) { nx = tox + dx[i]; ny = toy + dy[i]; if (0 <= nx && nx < N && 0 <= ny && ny <= M && nx != fromx && ny != fromy && MAT[nx][ny] == '1') { if (VIZ[nx][ny] == pas) { dfs2(nx, ny); } else if (VIZ[nx][ny] == 0) { dfs(nx, ny, tox, toy); if (VIZ[nx][ny] == -pas) { if (VIZ[tox][toy] > 0) { dfs2(tox, toy); } } } else if (VIZ[nx][ny] == -pas) { dfs2(tox, toy); } } } } void dfs2(int x, int y) { int i, nx, ny; if (VIZ[x][y] == -pas) return; if (VIZ[x][y] > 0) { ++cnt; VIZ[x][y] = -pas; } for (i = 0; i < 4; ++i) { nx = x + dx[i]; ny = y + dy[i]; if (0 <= nx && nx < N && 0 <= ny && ny <= M && MAT[nx][ny] == '1') { if (VIZ[nx][ny] > 0) { dfs2(nx, ny); } } } }