#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define MOD 105011 #define NMAX 505 #define MMAX NMAX*NMAX #define INF 0x3f3f3f3f #define pb push_back using namespace std; //FILE *fin = freopen("fisier.in", "r", stdin); //FILE *fout = freopen("fisier.out", "w", stdout); typedef pair pii; bool mat[NMAX][NMAX]; vector v[MMAX]; stack st; int low[MMAX], dfn[MMAX]; int nr, total; void compBC(int x, int y) { int a, b, i; vector v1; do { a = st.top().first; b = st.top().second; st.pop(); v1.pb(a); v1.pb(b); } while (a != x && b != y); sort(v1.begin(), v1.end()); a = 1; for (i = 1; i < v1.size(); ++i) if (v1[i] != v1[i - 1]) ++a; if (a > 3) total += a; } void DFS(int x, int p) { int i, y; low[x] = dfn[x] = ++nr; for (i = 0; i < v[x].size(); ++i) { y = v[x][i]; if (y == p) continue; if (dfn[y] == -1) { st.push({ x, y }); DFS(y, x); low[x] = min(low[x], low[y]); if (low[y] >= dfn[x]) compBC(x, y); } else low[x] = min(low[x], dfn[y]); } } int main() { int i, n, m, j; char ch; cin >> n >> m; for (i = 0; i < n; ++i) { for (j = 1; j <= m; ++j) { cin >> ch; mat[i][j] = ch - '0'; } } for (i = 0; i < n; ++i) { for (j = 1; j <= m; ++j) { if (mat[i][j]) { if (mat[i][j + 1]) { v[m*i + j].pb(m*i + j + 1); v[m*i + j + 1].pb(m*i + j); } if (mat[i + 1][j]) { v[m*i + j].pb(m*(i + 1) + j); v[m*(i + 1) + j].pb(m*i + j); } } } } memset(dfn, -1, sizeof(dfn)); DFS(1, -1); cout << total; return 0; }