SHARE
TWEET

Untitled

a guest Jan 22nd, 2020 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int ar[2001][2001];
  4. bool check[2001][2001];
  5. int n,m;
  6. int kx[8]={0,0,1,1,1,-1,-1,-1},
  7.     ky[8]={1,-1,1,-1,0,1,-1,0};
  8.  
  9. bool dfs(int x,int y){
  10.     if(check[x][y]==true)
  11.         return true;
  12.     check[x][y]=true;
  13.     for(int i=0;i<8;i++){
  14.         if(x+kx[i]>=1 && x+kx[i]<=n && y+ky[i]>=1 && y+ky[i]<=m && ar[x+kx[i]][y+ky[i]]==1 && check[x+kx[i]][y+ky[i]]==false){
  15.             dfs(x+kx[i],y+ky[i]);
  16.         }
  17.     }
  18.  
  19. }
  20.  
  21. int main(){
  22.  
  23.     int cnt=0;
  24.     scanf("%d %d",&n,&m);
  25.     for(int i=1;i<=n;i++){
  26.         for(int j=1;j<=m;j++){
  27.             char a;
  28.             scanf(" %c",&a);
  29.             ar[i][j]=a-'0';
  30.         }
  31.     }
  32.     for(int i=1;i<=n;i++){
  33.         for(int j=1;j<=m;j++){
  34.             if(check[i][j]==false && ar[i][j]==1){
  35.                 cnt++;
  36.                 dfs(i,j);
  37.             }
  38.         }
  39.     }
  40.     printf("%d",cnt);
  41.  
  42.     return 0;
  43. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top