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