fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN = 1e3 + 5;
  5.  
  6. long long n,m;
  7. long long visited[MaxN][MaxN];
  8. long long dx[5]={0,1,0,-1};
  9. long long dy[5]={1,0,-1,0};
  10.  
  11. char a[MaxN][MaxN];
  12.  
  13. long long bfs(long long i, long long j, char a[][MaxN], long long visited[][MaxN])
  14. {
  15.     queue<pair<long long,long long>> qu;
  16.  
  17.     qu.push({i,j});
  18.     visited[i][j]=true;
  19.  
  20.     long long cnt=0;
  21.  
  22.     if(a[i][j]=='x')
  23.     {
  24.         cnt++;
  25.     }
  26.  
  27.     while(!qu.empty())
  28.     {
  29.         long long x=qu.front().first;
  30.         long long y=qu.front().second;
  31.         qu.pop();
  32.  
  33.         for(long long t=0;t<4;t++)
  34.         {
  35.             long long newx=x+dx[t];
  36.             long long newy=y+dy[t];
  37.  
  38.             if(newx<1||newy<1||newx>n||newy>m)
  39.             {
  40.                 continue;
  41.             }
  42.  
  43.             if(a[newx][newy]!='#'&&visited[newx][newy]==-1)
  44.             {
  45.                 visited[newx][newy]=true;
  46.  
  47.                 if(a[newx][newy]=='x')
  48.                 {
  49.                     cnt++;
  50.                 }
  51.  
  52.                 qu.push({newx,newy});
  53.             }
  54.         }
  55.     }
  56.  
  57.     return cnt;
  58. }
  59.  
  60. void input()
  61. {
  62.     cin>>n>>m;
  63.  
  64.     for(long long i=1;i<=n;i++)
  65.     {
  66.         for(long long j=1;j<=m;j++)
  67.         {
  68.             cin>>a[i][j];
  69.             visited[i][j]=-1;
  70.         }
  71.     }
  72. }
  73.  
  74. void solve()
  75. {
  76.     vector<long long> res;
  77.  
  78.     for(long long i=1;i<=n;i++)
  79.     {
  80.         for(long long j=1;j<=m;j++)
  81.         {
  82.             if(a[i][j]!='#'&&visited[i][j]==-1)
  83.             {
  84.                 long long cnt=bfs(i,j,a,visited);
  85.  
  86.                 if(cnt>0)
  87.                 {
  88.                     res.push_back(cnt);
  89.                 }
  90.             }
  91.         }
  92.     }
  93.  
  94.     sort(res.begin(),res.end());
  95.  
  96.     for(long long x:res)
  97.     {
  98.         cout<<x<<" ";
  99.     }
  100. }
  101.  
  102. int main()
  103. {
  104.     ios_base::sync_with_stdio(0);
  105.     cin.tie(0);
  106.  
  107.     input();
  108.     solve();
  109. }
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kTsICu
language:
C++14 (gcc 8.3)
created:
2 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!