//Code by Patcas Csaba #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL long long #define PII pair #define VB vector #define VI vector #define VD vector #define VS vector #define VPII vector > #define VVI vector < VI > #define VVB vector < VB > #define FORN(i, n) for(int i = 0; i < (n); ++i) #define FOR(i, a, b) for(int i = (a); i <= (b); ++i) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define REPEAT do{ #define UNTIL(x) }while(!(x)); #define SZ size() #define BG begin() #define EN end() #define CL clear() #define X first #define Y second #define RS resize #define PB push_back #define MP make_pair #define ALL(x) x.begin(), x.end() #define IN_FILE "a.in" #define OUT_FILE "a.out" int n, m; VS a; VVI ind, g; VB good, was; VI ss; void df(int node, int startNode, int sp) { if (was[node]) { if (node == startNode && sp > 3) { FOR(i, 1, sp - 1) good[ss[i]] = true; } return; } was[node] = true; ss[sp] = node; FORN(i, g[node].SZ) { int aux = g[node][i]; df(aux, startNode, sp + 1); } } int main() { //Read data //freopen(IN_FILE, "r", stdin); //freopen(OUT_FILE, "w", stdout); cin >> n >> m; a.RS(n + 2); FOR(i, 0, n) { getline(cin, a[i]); a[i] = '#' + a[i] + '#'; } a[n + 1] = '#'; FORN(i, m) { a[0] += '#'; a[n + 1] += '#'; } ind.RS(n + 1, VI(m + 1)); int numNodes = 0; FOR(i, 1, n) FOR(j, 1, m) if (a[i][j] == '1') { ++numNodes; ind[i][j] = numNodes; } g.RS(numNodes + 1); FOR(i, 1, n) FOR(j, 1, m) if (a[i][j] == '1') { if (a[i - 1][j] == '1') g[ind[i][j]].PB(ind[i - 1][j]); if (a[i + 1][j] == '1') g[ind[i][j]].PB(ind[i + 1][j]); if (a[i][j + 1] == '1') g[ind[i][j]].PB(ind[i][j + 1]); if (a[i][j - 1] == '1') g[ind[i][j]].PB(ind[i][j - 1]); } //Solve good.RS(numNodes + 1, false); was.RS(numNodes + 1); ss.RS(numNodes + 1); FOR(i, 1, numNodes) if (!good[i]) { fill(ALL(was), false); df(i, i, 1); } int sol = 0; FOR(i, 1, numNodes) if (good[i]) ++sol; //Write data cout << sol; return 0; }