/* Catalin-Stefan Tiseanu Pre-written code is assembled from various sources found online. Big thanks to the community for that ! */ // Pre-written code below using namespace std; #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //START_CLEAN // always remove //START:mandatory #define DEBUG #ifndef NDEBUG # define assert_msg(condition, message) \ do { \ if (! (condition)) { \ std::cerr << "Assertion `" #condition "` failed in " << __FILE__ \ << " line " << __LINE__ << ": " << message << std::endl; \ std::exit(EXIT_FAILURE); \ } \ } while (false) #else # define ASSERT(condition, message) do { } while (false) #endif #ifdef DEBUG #define debug(args...) {dbg,args; cerr< std::ostream& operator <<(std::ostream& stream, const vector & v) { for (auto el : v) stream << el << " "; return stream; } template std::ostream& operator <<(std::ostream& stream, const vector> & v) { for (auto line : v) { for (auto el : line) stream << el << " "; stream << endl; } return stream; } template std::ostream& operator <<(std::ostream& stream, const pair & p) { stream << "( " << p.first << ", " << p.second << " )"; return stream; } class debugger { public: template void output (const T& v) { cerr << v << " "; } template debugger& operator , (const T& v) { output(v); return *this; } } dbg; //END:mandatory //////////////// // templates // //////////////// // general //template size template int size(const T& c) { return int(c.size()); } //template abs template T abs(T x) { return x < 0 ? -x : x; } //template sqr template T sqr(T x) { return x*x; } //template remin template bool remin(T& x, T y) { if (x <= y) return false; x = y; return true; } //template remax template bool remax(T& x, T y) { if (x >= y) return false; x = y; return true; } //template factorize template inline vector > factorize(T n) {vector > R;for (T i=2;n>1;){if (n%i==0){int C=0;for (;n%i==0;C++,n/=i);R.push_back(make_pair(i,C));} i++;if (i>n/i) i=n;}if (n>1) R.push_back(make_pair(n,1));return R;} //template toStr template string toStr(T x) { stringstream ss; ss << x; return ss.str(); } // other string maskToStr(long long x, int len) {stringstream ss; for (int i = 0; i < len; ++i) if (x >> i & 1) ss << "1"; else ss << "0"; return ss.str();} // misc #define EPS 1e-5 // types //template int64 typedef long long int64 ; //template uint64 typedef unsigned long long uint64 ; // shortcuts #define all(_xx) _xx.begin(), _xx.end() #define pb push_back #define vi vector #define vs vector #define vvi vector> #define vd vector #define vpii vector > #define vpdd vector > #define pii pair #define pll pair #define pdd pair #define mp(XX, YY) make_pair(XX, YY) #define fi first #define se second #define ll long long #define SS stringstream // for loops #define re(II, NN) for (int II(0), _NN(NN); (II) < (NN); ++(II)) #define fod(II, XX, YY) for (int II(XX), _YY(YY); (II) >= (_YY); --(II)) #define fo(II, XX, YY) for (int II(XX), _YY(YY); (II) <= (_YY); ++(II)) #define foreach(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it) // Useful hardware instructions #define bitcount __builtin_popcount #define gcd __gcd // Useful all around #define checkbit(n,b) ( (n >> b) & 1) #define DREP(a) sort(a.begin(), a.end());a.erase(unique(a.begin(), a.end()),a.end()) #define INDEX(arr,ind) (lower_bound(arr.begin(), arr.end(),ind)-arr.begin()) #define PAUSE cerr << "Press any key to continue ..."; char xxxx; scanf("%c", &xxxx); #define fill(xx,val) memset(xx, val, sizeof(xx)) struct Scanner { char* curPos; const static int BUF_SIZE = (2000000); char input[BUF_SIZE]; FILE * fin; void init(FILE * _fin) { fin = _fin; fread(input, 1, sizeof(input), fin); curPos = input; } Scanner() {;} inline void ensureCapacity() { int size = input + BUF_SIZE - curPos; if (size < 100) { memcpy(input, curPos, size); fread(input + size, 1, BUF_SIZE - size, fin); curPos = input; } } inline int nextInt() { ensureCapacity(); while (!isdigit(*curPos) && *curPos != '-') ++curPos; int res = 0; int sign = 1; if (*curPos == '-') sign = -1, ++curPos; while (*curPos >= '0' && *curPos <= '9') res = res * 10 + (*(curPos++) & 15); return sign * res; } } Sc; // code starts here struct BiconnectedGraph { // doit by edges // result[i] = biconnected component of node i (by edges) int N; vvi g; vi depth, parent, low; vector visited; struct UnionFind { vector p; int gp(int x) { if (p[x] != x) { p[x] = gp(p[x]); } return p[x]; } void un(int a, int b) { p[gp(a)] = gp(b); } void init(int n) { p = vi(n); for (int i = 0; i < n; ++i) { p[i] = i; } } UnionFind() {;} UnionFind(int n) {init(n);} } uf; void dfs_low(int x) { visited[x] = true; low[x] = depth[x]; for (auto it : g[x]) { if (!visited[it]) { depth[it] = depth[x] + 1; parent[it] = x; dfs_low(it); low[x] = min(low[x], low[it]); if (low[it] <= depth[x]) { uf.un(x, it); } } else if (it != parent[x]) { low[x] = min(low[x], depth[it]); } } } vi getByEdges(const vvi & adj) { g = adj; N = g.size(); uf.init(N); visited = vector(N, false); parent = vi(N, -1); depth = vi(N, 0); low = vi(N, -1); re (i, N) if (!visited[i]) dfs_low(i); vi result; re (i, N) result.pb(uf.p[i]); return result; } } G; #define MAX_N (1<<9) int N, M, res; char board[MAX_N][MAX_N]; vvi adj; inline int getIndex(int x, int y) {return (x - 1) * M + y;} inline void addEdge(vvi & adj, int x, int y, int nx, int ny) { if (board[x][y] != '1' || board[nx][ny] != '1') return; adj[getIndex(x, y)].pb(getIndex(nx, ny)); adj[getIndex(nx, ny)].pb(getIndex(x, y)); } void constructGraph() { adj.resize(N * M + 1); fo (i, 1, N) fo (j, 1, M) { if (i > 1) addEdge(adj, i, j, i - 1, j); if (i < N) addEdge(adj, i, j, i + 1, j); if (j < M) addEdge(adj, i, j, i, j + 1); if (j > 1) addEdge(adj, i, j, i, j - 1); } } unordered_map um; int main() { scanf("%d %d \n", &N, &M); fo (i, 1, N) gets(board[i] + 1); constructGraph(); vi result = G.getByEdges(adj); fo (i, 1, N * M) um[result[i]]++; fo (i, 1, N * M) if (um[result[i]] >= 4) ++res; printf("%d\n", res); return 0; }