Advertisement
Guest User

Untitled

a guest
Jan 22nd, 2020
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.92 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement