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,d[1005][1005];
  13. bool x[1005][1005],vs[1005][1005];
  14. std::vector<pair<int,int>> a[1005][1005];
  15. queue<pair<int,int>> tr;
  16. void cv(int &dem,int i,int j)
  17. {
  18.     dem+=!x[i][j+1];
  19.     dem+=!x[i][j-1];
  20.     dem+=!x[i+1][j];
  21.     dem+=!x[i-1][j];
  22. }
  23. void bfs(pair<int,int> i,int &dientich,int &chuvi)
  24. {
  25.     queue<pair<int,int>> q;
  26.     pair<int,int> c;
  27.     q.push(i);
  28.     vs[i.fi][i.se]=1;
  29.     dientich++;
  30.     cv(chuvi,i.fi,i.se);
  31.     while(!q.empty())
  32.     {
  33.         c=q.front();
  34.         q.pop();
  35.         for(pair<int,int> &j:a[c.fi][c.se])
  36.         {
  37.             if(!vs[j.fi][j.se])
  38.             {
  39.                 cv(chuvi,j.fi,j.se);
  40.                 dientich++;
  41.                 d[j.fi][j.se]=d[c.fi][c.se]+1;
  42.                 vs[j.fi][j.se]=1;
  43.                 q.push(j);
  44.             }
  45.         }
  46.     }
  47. }
  48. main()
  49. {
  50.     ios;
  51.     freo;
  52.     cin>>n>>m;
  53.     for(int i=1;i<=n;i++)
  54.     {
  55.         for(int j=1;j<=m;j++)
  56.         {
  57.             cin>>x[i][j];
  58.             if(x[i][j])
  59.                 tr.push({i,j});
  60.         }
  61.     }
  62.     for(int i=1;i<=n;i++)
  63.     {
  64.         for(int j=1;j<=m;j++)
  65.         {
  66.             if(x[i][j]&&x[i][j+1])
  67.             {
  68.                 a[i][j].push_back({i,j+1});
  69.                 a[i][j+1].push_back({i,j});
  70.             }
  71.             if(x[i][j]&&x[i+1][j])
  72.             {
  73.                 a[i][j].push_back({i+1,j});
  74.                 a[i+1][j].push_back({i,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.         }
  87.     }
  88.     pair<int,int> c;
  89.     int dientich=0,chuvi=0,MAXdt=0,MAXchuvi=0;
  90.     while(!tr.empty())
  91.     {
  92.         dientich=0;
  93.         chuvi=0;
  94.         c=tr.front();
  95.         tr.pop();
  96.         if(!vs[c.fi][c.se])
  97.         {
  98.             bfs(c,dientich,chuvi);
  99.             MAXdt=max(MAXdt,dientich);
  100.             MAXchuvi=max(MAXchuvi,chuvi);
  101.         }
  102.     }
  103.     cout<<MAXdt<<"\n"<<MAXchuvi;
  104. }
  105.  
Success #stdin #stdout 0.01s 28524KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
0
https://ideone.com/cRWgpV
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!