Advertisement
nazmulsarker

Untitled

Dec 8th, 2015
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.52 KB | None | 0 0
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<queue>
  4. #define max 200
  5. using namespace std;
  6. int color[max][max],count=0,n;
  7. char mat[max][max];
  8. int X[8] ={-1,-1,-1,0,0,1,1,1};
  9. int Y[8] ={-1,0,1,-1,1,-1,0,1};
  10.  
  11. void bfs(int x,int y)
  12. {
  13. int ux,uy,vx,vy,i,j;
  14. queue<int>Q;
  15. Q.push(x);
  16. Q.push(y);
  17. color[x][y]=1;
  18. while(!Q.empty())
  19. {
  20. ux = Q.front();
  21. Q.pop();
  22. uy = Q.front();
  23. Q.pop();
  24. for(i=0; i<8; i++)
  25. {
  26. vx=ux+X[i];
  27. vy=uy+Y[i];
  28. if((vx>=0 && vx<n) && (uy>=0 &&uy<n) && mat[vx][vy]=='1')
  29. {
  30. if(color[vx][vy]==0)
  31. {
  32. color[vx][vy]=1;
  33. Q.push(vx);
  34. Q.push(vy);
  35.  
  36. }
  37. }
  38. }
  39.  
  40. }
  41.  
  42. }
  43. int main()
  44. {
  45. int i,j,k,l,x=0;
  46. while(scanf("%d",&n)==1)
  47. {
  48. x++;
  49. memset(color,0,sizeof(color));
  50. memset(mat,'\0',sizeof(mat));
  51. getchar();
  52. for(i=0; i<n; i++)
  53. {
  54. for(j=0; j<n; j++)
  55. {
  56. scanf(" %c",&mat[i][j]);
  57. }
  58. }
  59.  
  60. for(i=0; i<n; i++)
  61. {
  62. for(j=0; j<n; j++)
  63. {
  64.  
  65. if(color[i][j]==0 && mat[i][j]=='1')
  66. {
  67. bfs(i,j);
  68. count++;
  69. }
  70. }
  71.  
  72. }
  73. printf("Image number %d contains %d war eagles.\n",x,count);
  74. count =0;
  75. }
  76.  
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement