fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl cout<<"\n";
  3. #define fi first
  4. #define int long long
  5. #define se second
  6. #define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  7. #define op freopen
  8. #define TXT "test"
  9. #define freo if(fopen(TXT".inp","r")){op(TXT".inp","r",stdin);op(TXT".out","w",stdout);}
  10.  
  11. using namespace std;
  12. int n,m;
  13. bool x[1005][1005],vs[1005][1005];
  14. char ch[1005][1005];
  15. vector<pair<int,int>> a[1005][1005];
  16. queue<pair<int,int>>tr;
  17. void bfs(pair<int,int> i)
  18. {
  19.     vs[i.fi][i.se]=1;
  20.     for(pair<int,int> &j:a[i.fi][i.se])
  21.     {
  22.         if(!vs[j.fi][j.se])
  23.         {
  24.             bfs(j);
  25.         }
  26.     }
  27. }
  28. main()
  29. {
  30.     ios;
  31.     freo;
  32.     cin>>n>>m;
  33.     for(int i=1;i<=n;i++)
  34.     {
  35.         for(int j=1;j<=m;j++)
  36.         {
  37.             cin>>ch[i][j];
  38.             if(ch[i][j]=='#')
  39.             {
  40.                 x[i][j]=1;
  41.             }
  42.             else
  43.             {
  44.                 x[i][j]=0;
  45.                 tr.push({i,j});
  46.             }
  47.         }
  48.     }
  49.     for(int i=1;i<=n;i++)
  50.     {
  51.         for(int j=1;j<=m;j++)
  52.         {
  53.             if(!x[i][j]&&!x[i][j+1])
  54.             {
  55.                 a[i][j].push_back({i,j+1});
  56.                 a[i][j+1].push_back({i,j});
  57.             }
  58.             if(!x[i][j]&&!x[i+1][j])
  59.             {
  60.                 a[i][j].push_back({i+1,j});
  61.                 a[i+1][j].push_back({i,j});
  62.             }
  63.             if(!x[i][j]&&!x[i][j-1])
  64.             {
  65.                 a[i][j].push_back({i,j-1});
  66.                 a[i][j-1].push_back({i,j});
  67.             }
  68.             if(!x[i][j]&&!x[i-1][j])
  69.             {
  70.                 a[i][j].push_back({i-1,j});
  71.                 a[i-1][j].push_back({i,j});
  72.             }
  73.         }
  74.     }
  75.     int dem=0;
  76.     pair<int,int> c;
  77.     while(!tr.empty())
  78.     {
  79.         c=tr.front();
  80.         tr.pop();
  81.         if(!vs[c.fi][c.se])
  82.         {
  83.             dem++;
  84.             bfs(c);
  85.         }
  86.     }
  87.     cout<<dem;
  88. }
  89.  
Success #stdin #stdout 0.01s 27740KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wT7xKV
language:
C++ (gcc 8.3)
created:
12 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!