fork download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<queue>
  6. #define max 105
  7. using namespace std;
  8.  
  9. char ch[max][max];
  10. int mat[max][max]={0};
  11. int mark[max][max]={0};
  12. int marking,m,n;
  13. queue<int> qi,qj;
  14.  
  15. void push_queue(int i,int j){
  16.        qi.push(i);
  17.        qj.push(j);
  18. }
  19.  
  20. void pop_queue(){
  21.    qi.pop();
  22.    qj.pop();    
  23. }
  24.  
  25. void checkadj(int i,int j) {
  26.      mat[i][j] = 0;
  27.      mark[i][j] = 1;
  28.      if(mat[i-1][j] == 1 && mark[i-1][j]==0) {
  29.        mark[i][j] = 1;
  30.        mat[i][j] = 0;
  31.        push_queue(i-1,j);
  32.      }
  33.  
  34.      if(mat[i-1][j-1] == 1 && mark[i-1][j-1] == 0) {
  35.        mark[i-1][j-1] = 1;
  36.        mat[i-1][j-1] = 0;
  37.        push_queue(i-1,j-1);
  38.      }
  39.  
  40.      if(mat[i-1][j+1] == 1 && mark[i-1][j+1] == 0) {
  41.        mark[i-1][j+1] = 1;
  42.        mat[i-1][j+1] = 0;
  43.        push_queue(i-1,j+1);
  44.      }
  45.  
  46.      if(mat[i][j-1] == 1 && mark[i][j-1] == 0) {
  47.        mark[i][j-1] = 1;
  48.        mat[i][j-1] = 0;       
  49.        push_queue(i,j-1);
  50.      }
  51.  
  52.      if(mat[i][j+1] == 1 && mark[i][j+1] == 0) {
  53.        mark[i][j+1] = 1;
  54.        mat[i][j+1] = 0;       
  55.        push_queue(i,j+1);
  56.      }
  57.  
  58.      if(mat[i+1][j-1] == 1 && mark[i+1][j-1] == 0) {
  59.        mark[i+1][j-1] = 1 ;
  60.        mat[i+1][j-1] = 0 ;       
  61.        push_queue(i+1,j-1);
  62.      }
  63.  
  64.      if(mat[i+1][j] == 1 && mark[i+1][j] == 0) {
  65.        mark[i+1][j] = 1;
  66.        mat[i+1][j] = 0;       
  67.        push_queue(i+1,j);
  68.      }
  69.  
  70.      if(mat[i+1][j+1] == 1 && mark[i+1][j+1] == 0) {
  71.        mark[i+1][j+1] = 1;
  72.        mat[i+1][j+1] = 0;       
  73.        push_queue(i+1,j+1);
  74.      }
  75. }
  76.  
  77. void traverse(int i,int j) {
  78.    int ti,tj,x,y;
  79.    push_queue(i,j);
  80.    while(!qi.empty() && !qj.empty()) {
  81.          ti= qi.front();
  82.          tj= qj.front();
  83.          pop_queue();
  84.          checkadj(ti,tj);
  85.    }  
  86. }
  87.  
  88. void exploregrid() {
  89.    int x,y;
  90.    for(x=1;x<=m;x++){
  91.      for(y=1;y<=n;y++){
  92.         if(mat[x][y] == 1) {
  93.                      traverse(x,y);
  94.                      marking++;
  95.         }
  96.      }        
  97.    }
  98. }
  99.  
  100. int main(){
  101.     int i,j;
  102.     while(1) {
  103.       scanf("%d%d",&m,&n);
  104.       if(m==0 && n==0) break;
  105.       for(i=0;i<m;i++){
  106.           scanf("%s",ch[i]);   
  107.       }
  108.       for(i=0;i<=4;i++) mat[0][i]=0;
  109.       for(i=1;i<=m;i++){
  110.         for(j=1;j<=n;j++) {
  111.            if(ch[i-1][j-1]=='@') mat[i][j]=1;   
  112.            else mat[i][j]=0;
  113.         }               
  114.       }
  115.       m=m+1;
  116.        for(i=0;i<=4;i++) mat[m][i]=0;
  117.       n=n+1;
  118.     /*  for(i=0;i<=m;i++){
  119.         for(j=0;j<=n;j++) {
  120.            cout<<mat[i][j]<<" ";   
  121.         }               
  122.         printf("\n");
  123.       }
  124. */
  125.       marking=0;
  126.       exploregrid();
  127.       printf("%d\n",marking);
  128.     /*  for(i=1;i<=m;i++) 
  129.         for(j=1;i<=n;j++)
  130.            mat[i][j] = mark[i][j] = 0;                  */
  131.       memset(mat,0,sizeof(mat));
  132. memset(mark,0,sizeof(mark));
  133.     }
  134.     return 0;         
  135. }
  136.  
Success #stdin #stdout 0s 2964KB
comments (?)
stdin
copy 
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
stdout
copy 
0
1
2
2
https://ideone.com/FnlxUz
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 years ago
visibility:
secret

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!