#include #define NMAX 512 char A[NMAX][NMAX]; int M, N; void ReadInput() { scanf("%d %d", &M, &N); for (int i = 1; i <= M; i++) scanf("%s", &(A[i][1])); } int drow[4] = {-1, 0, +1, 0}; int dcol[4] = {0, +1, 0, -1}; int lmin[NMAX][NMAX], level[NMAX][NMAX], parent[NMAX][NMAX][2], ans; char visited[NMAX][NMAX], touched_from_below[NMAX][NMAX]; void DFS(short int i, short int j) { short int ii, jj, k; visited[i][j] = 1; lmin[i][j] = level[i][j]; fprintf(stderr, "enter %d %d\n", i, j); for (k = 0; k < 4; k++) { ii = i + drow[k]; jj = j + dcol[k]; if (A[ii][jj] == '1') { if (parent[i][j][0] == ii && parent[i][j][1] == jj) continue; if (!visited[ii][jj]) { parent[ii][jj][0] = i; parent[ii][jj][1] = j; level[ii][jj] = level[i][j] + 1; DFS(ii, jj); if (lmin[ii][jj] < lmin[i][j]) lmin[i][j] = lmin[ii][jj]; } else { touched_from_below[ii][jj] = 1; if (level[ii][jj] < lmin[i][j]) lmin[i][j] = level[ii][jj]; } } } fprintf(stderr, "exit %d %d: %d %d %d\n", i, j, level[i][j], lmin[i][j], touched_from_below[i][j]); if (lmin[i][j] < level[i][j] || touched_from_below[i][j]) ans++; } void StartDFS() { short int i, j; ans = 0; for (i = 1; i <= M; i++) for (j = 1; j <= N; j++) if (A[i][j] == '1' && !visited[i][j]) { level[i][j] = 0; DFS(i, j); } } int main() { ReadInput(); StartDFS(); printf("%d\n", ans); return 0; }