fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define pb push_back
  5. #define fi first
  6. #define se second
  7. #define mp make_pair
  8. #define all(cont) cont.begin(), cont.end()
  9.  
  10. class Graph
  11. {
  12. public:
  13.     ll **pond;
  14.     bool **visited;
  15.     ll **comp;
  16.     ll COLOR;
  17.     ll n;
  18.     ll m;
  19.     void init()
  20.     {
  21.         cin >> n >> m;
  22.         pond = new ll*[n];
  23.         comp = new ll*[n];
  24.         visited = new bool*[n];
  25.         for (ll i = 0; i < n; i++)
  26.         {
  27.             pond[i] = new ll[m];
  28.             visited[i] = new bool[m];
  29.             comp[i] = new ll[m];
  30.             for (ll j = 0; j < m; j++)
  31.             {
  32.  
  33.                 comp[i][j] = -1;
  34.                 visited[i][j] = false;
  35.                 cin >> pond[i][j];
  36.             }
  37.         }
  38.  
  39.         COLOR = 0;
  40.  
  41.         for (ll i = 0; i < n; i++)
  42.         {
  43.             for (ll j = 0; j < m; j++)
  44.             {
  45.                 if (pond[i][j] != 0 && !visited[i][j])
  46.                 {
  47.                     COLOR++;
  48.                     bfs(i, j);
  49.                 }
  50.             }
  51.         }
  52.         ll ans = 0;
  53.         for (ll i = 0; i < n; i++)
  54.         {
  55.             for (ll j = 0; j < m; j++)
  56.             {
  57.                 if (pond[i][j] == 0)
  58.                 {
  59.                     unordered_set<ll>included;
  60.                     ll curr = 0;
  61.                     if (i > 0 && included.find(comp[i - 1][j]) == included.end())
  62.                     {
  63.                         included.insert(comp[i-1][j]);
  64.                         curr += pond[i - 1][j];
  65.                     }
  66.                     if (i < n - 1 && included.find(comp[i + 1][j]) == included.end())
  67.                     {
  68.                         included.insert(comp[i+1][j]);
  69.                         curr += pond[i + 1][j];
  70.                     }
  71.                     if (j > 0 && included.find(comp[i][j - 1]) == included.end())
  72.                     {
  73.                         included.insert(comp[i][j-1]);
  74.                         curr += pond[i][j - 1];
  75.                     }
  76.                     if (j < m - 1 && included.find(comp[i][j + 1]) == included.end())
  77.                     {
  78.                         included.insert(comp[i][j+1]);
  79.                         curr += pond[i][j + 1];
  80.                     }
  81.                     // cout<<i<<" "<<j<<" "<<curr<<endl;
  82.                     ans = max(ans, curr);
  83.                 }
  84.             }
  85.         }
  86.         cout << ans << endl;
  87.     }
  88.     void bfs(ll srcx, ll srcy)
  89.     {
  90.  
  91.         queue<pair<ll, ll>>q;
  92.         q.push(mp(srcx, srcy));
  93.         visited[srcx][srcy] = true;
  94.         pair<ll, ll>curr;
  95.         vector<pair<ll, ll>>forsizecolor;
  96.         ll size = 0;
  97.         while (!q.empty())
  98.         {
  99.             curr = q.front();
  100.             q.pop();
  101.             size++;
  102.             forsizecolor.pb(curr);
  103.             if (curr.fi < n - 1 && pond[curr.fi + 1][curr.se] != 0 && !visited[curr.fi + 1][curr.se])
  104.             {
  105.                 visited[curr.fi + 1][curr.se] = true;
  106.                 q.push(mp(curr.fi + 1, curr.se));
  107.             }
  108.             if (curr.fi > 0 && pond[curr.fi - 1][curr.se] != 0 && !visited[curr.fi - 1][curr.se])
  109.             {
  110.                 visited[curr.fi - 1][curr.se] = true;
  111.                 q.push(mp(curr.fi - 1, curr.se));
  112.             }
  113.             if (curr.se < n - 1 && pond[curr.fi][curr.se + 1] != 0 && !visited[curr.fi][curr.se + 1])
  114.             {
  115.                 visited[curr.fi][curr.se + 1] = true;
  116.                 q.push(mp(curr.fi, curr.se + 1));
  117.             }
  118.             if (curr.se > 0 && pond[curr.fi][curr.se - 1] != 0 && !visited[curr.fi][curr.se - 1])
  119.             {
  120.                 visited[curr.fi][curr.se - 1] = true;
  121.                 q.push(mp(curr.fi, curr.se - 1));
  122.             }
  123.         }
  124.         for (auto it : forsizecolor)
  125.         {
  126.             comp[it.fi][it.se] = COLOR;
  127.             pond[it.fi][it.se] = size;
  128.         }
  129.         // for(ll i=0;i<n;i++)
  130.         // {
  131.         //     for(ll j=0;j<m;j++)
  132.         //         cout<<comp[i][j]<<" ";
  133.         //     cout<<endl;
  134.         // }
  135.         // cout<<endl;
  136.     }
  137.  
  138. };
  139.  
  140. int main()
  141. {
  142.  
  143.     ios::sync_with_stdio(0);
  144.     cin.tie(0);
  145. #ifndef ONLINE_JUDGE
  146.     freopen("input.txt", "r", stdin);
  147.     freopen("output.txt", "w", stdout);
  148. #endif
  149.  
  150.  
  151.  
  152.  
  153.     Graph G;
  154.     G.init();
  155.  
  156.     return 0;
  157.  
  158. }
Success #stdin #stdout 0s 4408KB
comments (?)
stdin
copy 
3 5
1 0 0 0 1
1 0 1 1 1
0 1 0 0 0
stdout
copy 
7
https://ideone.com/XusaC2
language:
C++14 (gcc 8.3)
created:
5 years 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!