#include <string> // std::string #include <iostream> // std::cout #include <sstream> #include <fstream> #include <vector> #include <algorithm> #include <cmath> using namespace std; #define LOCAL_DEBUG_ int n; int m; int a[501][501]; int sol[501][501]; int n_up(int i, int j) { if (i-1<0) return 0; return a[i-1][j]; } int n_down(int i, int j) { if (i+1>=n) return 0; return a[i+1][j]; } int n_left(int i, int j) { if (j-1<0) return 0; return a[i][j-1]; } int n_right(int i, int j) { if (j+1>=m) return 0; return a[i][j+1]; } int Enc(int i, int j) { return i*501 + j; } int DecI(int e) { return e/501; } int DecJ(int e) { return e%501; } int PathContains(vector<int> &path, int i, int j) { return path.end() != find(path.begin(), path.end(), Enc(i, j)); } int AreNeighbour(int si, int sj, int i, int j) { return (si-i==0 && abs(sj-j)<=1) || (abs(si-i)<=1 && sj-j==0); } void DFS(int si, int sj, vector<int> path) { int pathCount = path.size(); int i = DecI(path[pathCount-1]); int j = DecJ(path[pathCount-1]); // if (sol[i][j] == 1) return; // cout << "DFS called : "; for(int k=0; k<path.size(); k++) // cout << " (" << DecI(path[k]) << "," << DecJ(path[k]) << ")"; // cout << endl; if (path.size() >= 4 && AreNeighbour(si, sj, i, j)) { // cout << "SOLUTION" << endl; // solution for(int k=0; k<pathCount; k++) sol[DecI(path[k])][DecJ(path[k])]=1; } else { // try to DFS... if (n_up(i,j) && !PathContains(path, i-1, j)) { path.push_back(Enc(i-1, j)); DFS(si, sj, path); path.pop_back(); } if (n_down(i,j) && !PathContains(path, i+1, j)) { path.push_back(Enc(i+1, j)); DFS(si, sj, path); path.pop_back(); } if (n_left(i,j) && !PathContains(path, i, j-1)) { path.push_back(Enc(i, j-1)); DFS(si, sj, path); path.pop_back(); } if (n_right(i,j) && !PathContains(path, i, j+1)) { path.push_back(Enc(i, j+1)); DFS(si, sj, path); path.pop_back(); } } } int main() { // read input #ifdef LOCAL_DEBUG std::ifstream in("3bigtest.in"); std::streambuf *cinbuf = std::cin.rdbuf(); std::cin.rdbuf(in.rdbuf()); #endif string tmp; getline(cin, tmp); stringstream ss(tmp); ss >> n; ss >> m; for(int i=0; i<n; i++) { string s; getline(cin, s); for(int j=0; j<m; j++) { if (s[j]=='0') a[i][j]=0; else a[i][j] = 1; } } #ifdef LOCAL_DEBUG std::cin.rdbuf(cinbuf); #endif // DFS ... for(int i=0; i<n; i++) for(int j=0; j<m; j++) { vector<int> path; path.push_back(Enc(i,j)); if (a[i][j]==1 && sol[i][j]==0) DFS(i,j, path); } // count remaining 1s //cout << endl; int c=0; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { //cout << sol[i][j]; c += sol[i][j]; } // cout << endl; } // write solution cout << c; return 0; }