fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define for1(i,a,b) for(int i=a;i<=b;i++)
  6. #define for0(i,a,b) for(int i=a;i<b;i++)
  7. #define vll(v) v.begin(),v.end()
  8. #define ii pair<int,int>
  9. #define el '\n'
  10. #define pb push_back
  11. const int N=1e6;
  12. const int MOD=1e9+7;
  13. int f[1011][1011];
  14. int a[1011][1011],vt[1011][1011];
  15.  int n,m,k,ans=0;
  16.  struct ju{
  17.   int fii,se,th,fi;
  18.  };
  19.  int get(int x,int y,int x_,int y_){
  20.   return f[x_][y_]-f[x][y_]-f[x_][y]+f[x][y];
  21.  }
  22.  void solve(int xx,int yy){
  23.      queue<ju>q;
  24.  for1(i,xx,xx+k-1)
  25.   for1(j,yy,yy+k-1){
  26.    if(a[i][j]==1) return;
  27.   }
  28.   ans++;
  29.  // cout<<ans<<el;
  30.   q.push({xx,yy,xx+k-1,yy+k-1});
  31.   while(!q.empty()){
  32.  
  33.         ju ff=q.front();
  34.   q.pop();
  35.   int x=ff.fii,y=ff.se,x_=ff.th,y_=ff.fi;
  36.   //cout<<x<<' '<<y<<el;
  37. vt[x][y]=1;
  38.  
  39.      if(y_+1<=m&&vt[x][y+1]==0&&get(x-1,y_,x_,y_+1)==0) {
  40.             q.push({x,y+1,x_,y_+1});
  41.             vt[x][y+1]=1;
  42.      }
  43.  
  44.  
  45.       if(x_+1<=n&&vt[x+1][y]==0&&get(x_,y-1,x_+1,y_)==0) {
  46.             q.push({x+1,y,x_+1,y_});
  47.             vt[x+1][y]=1;
  48.       }
  49.  
  50.  
  51.  
  52.  
  53.       if(x-1>=1&&vt[x-1][y]==0&&get(x-1-1,y-1,x_-1,y_)==0) {
  54.             q.push({x-1,y,x_-1,y_});
  55.             vt[x-1][y]=1;
  56.       }
  57.  
  58.  
  59.  
  60.       if(y-1>=1&&vt[x][y-1]==0&&get(x-1,y-2,x_,y-1)==0) {
  61.             q.push({x,y-1,x_,y_-1});
  62.            vt[x][y-1]=1;
  63.       }
  64.  
  65.  
  66.   }
  67.  
  68.  }
  69. signed main(){
  70.  ios_base::sync_with_stdio(0);
  71.  cin.tie(0);
  72.  cout.tie(0);
  73.  /*
  74.  freopen("a.INP","r",stdin);
  75.  freopen("a.OUT","w",stdout);
  76. 4 8 3
  77. 0 0 0 1 0 0 0 0
  78. 0 0 0 0 0 0 0 0
  79. 0 0 0 0 0 0 0 0
  80. 0 0 0 0 0 1 1 0
  81.  
  82.  */
  83.  
  84.  cin>>n>>m>>k;
  85.  for1(i,1,n)
  86.    for1(j,1,m)
  87.   cin>>a[i][j];
  88.  
  89.   for1(i,1,n)
  90.     for1(j,1,m){
  91.      f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];
  92.     }
  93.  
  94.    for1(i,1,n-k+1)
  95.     for1(j,1,m-k+1){
  96.       if(a[i][j]==0&&vt[i][j]==0){
  97.        // ans++;
  98.         solve(i,j);
  99.       }
  100.     }
  101.     cout<<ans;
  102.  return 0;
  103. }
  104.  
  105.  
  106.  
  107.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/7RsHJp
language:
C++14 (gcc 8.3)
created:
4 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!