#include // std::string #include // std::cout #include #include #include #include #include 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 &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 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= 4 && AreNeighbour(si, sj, i, j)) { // cout << "SOLUTION" << endl; // solution for(int k=0; k> n; ss >> m; for(int i=0; i 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