fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #pragma GCC optimize ("Ofast")
  4. using namespace std;
  5.  
  6. int rows,cols;
  7. int ans=0;
  8. int area;
  9.  
  10. inline bool controlla(vector<vector<int>>&m,int i,int j){
  11.     if(m[i][j])
  12.         return false;
  13.     if(i>=2){
  14.         if(m[i-1][j]&&m[i-2][j])
  15.             return false;
  16.         if(j>=2){
  17.             if(m[i-1][j-1]&&m[i-2][j-2])
  18.                 return false;
  19.         }
  20.         if(j<=cols-3){
  21.             if(m[i-2][j+2]&&m[i-1][j+1])
  22.                 return false;
  23.         }
  24.     }
  25.     if(i<=rows-3){
  26.         if(m[i+1][j]&&m[i+2][j])
  27.             return false;
  28.         if(j>=2){
  29.             if(m[i+1][j-1]&&m[i+2][j-2])
  30.                 return false;
  31.         }
  32.         if(j<=cols-3){
  33.             if(m[i+1][j+1]&&m[i+2][j+2])
  34.                 return false;
  35.         }
  36.     }
  37.     if(j>=2){
  38.         if(m[i][j-1]&&m[i][j-2])
  39.             return false;
  40.     }
  41.     if(j<=cols-3){
  42.         if(m[i][j+1]&&m[i][j+2])
  43.             return false;
  44.     }
  45.     if(j>0 && j<cols-1){
  46.         if(m[i][j-1]&&m[i][j+1])
  47.             return false;
  48.     }
  49.     if(i>0 && i<rows-1){
  50.         if(m[i-1][j]&&m[i+1][j])
  51.             return false;
  52.     }
  53.     if(j>0 && i>0 && j<cols-1 && i<rows-1){
  54.         if(m[i-1][j-1]&&m[i+1][j+1])
  55.             return false;
  56.         if(m[i-1][j+1]&&m[i+1][j-1])
  57.             return false;
  58.     }
  59.  
  60.     return true;
  61. }
  62.  
  63.  
  64. void solve(vector<vector<int>>&m,int count,int i,int j){
  65.     if(j>=cols){
  66.         i++;
  67.         j=0;
  68.     }
  69.     if(i==rows){
  70.         if(count>ans)
  71.             ans=count;
  72.         return;
  73.     }
  74.     if((area-((i)*cols+j)+count)<=ans)
  75. 		return;	
  76.     if(controlla(m,i,j)){
  77.         m[i][j]=1;
  78.         solve(m,count+1,i,j+1);
  79.         m[i][j]=0;
  80.     }
  81.     solve(m,count,i,j+1);
  82. }
  83.  
  84. int main(){
  85. ios::sync_with_stdio(false);
  86. cin.tie(0);
  87.     cin>>rows>>cols;
  88. vector<vector<int>>m(rows,vector<int>(cols));
  89.     area=rows*cols;
  90.     for(int i=0;i<rows;i++)
  91.         for(int j=0;j<cols;j++)
  92.             cin>>m[i][j];
  93.  
  94.     solve(m,0,0,0);
  95.  
  96.     cout<<ans;
  97.  
  98.     return 0;
  99. }
  100.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
1 10
0 0 0 0 0 0 0 0 0 0
stdout
copy 
7
https://ideone.com/NJtIno
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!