fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3.  
  4. using namespace std;
  5.  
  6. struct info {
  7.     int x, y;
  8. };
  9.  
  10. int m, n;
  11. int a[1111][1111];
  12. int lab[1111 * 1111];
  13. int dx[] = {0, 0, 1, -1};
  14. int dy[] = {-1, 1, 0, 0};
  15.  
  16. unordered_map<int, int> freq;
  17.  
  18. int getIndex(int x, int y) {
  19.     return (x - 1) * n + y;
  20. }
  21.  
  22. void init() {
  23.     for (int i = 0; i < m * n; i += 1) {
  24.         lab[i] = -1;
  25.     }
  26. }
  27.  
  28. int Find(int u) {
  29.     if (lab[u] < 0) return u;
  30.  
  31.     lab[u] = Find(lab[u]);
  32.  
  33.     return lab[u];
  34. }
  35.  
  36. void Union(int u, int v) {
  37.     int r1 = Find(u);
  38.     int r2 = Find(v);
  39.  
  40.     if (r1 == r2) return;
  41.  
  42.     if (abs(r1) < abs(r2)) swap(r1, r2);
  43.  
  44.     lab[r1] += lab[r2];
  45.     lab[r2] = r1;
  46. }
  47.  
  48. int32_t main() {
  49.     ios_base::sync_with_stdio(false);
  50.     cin.tie(NULL);
  51.  
  52.     freopen("ISLANDS.INP", "r", stdin);
  53.     freopen("ISLANDS.OUT", "w", stdout);
  54.  
  55.     cin >> m >> n;
  56.  
  57.     init();
  58.  
  59.     int high = 0;
  60.     for (int i = 1; i <= m; i += 1) {
  61.         for (int j = 1; j <= n; j += 1) {
  62.             cin >> a[i][j];
  63.             high = max(high, a[i][j]);
  64.             freq[a[i][j]] += 1;
  65.         }
  66.     }
  67.  
  68.     int res = 0;
  69.  
  70.     for (int k = high; k >= 0; k -= 1) {
  71.         if (freq[k] > 0) {
  72.  
  73.             unordered_set<int> cnt;
  74.  
  75.             for (int i = 1; i <= m; i += 1) {
  76.                 for (int j = 1; j <= n; j += 1) {
  77.  
  78.                     if (a[i][j] < k) continue;
  79.  
  80.                     for (int d = 0; d < 4; d += 1) {
  81.                         info h = {i + dx[d], j + dy[d]};
  82.  
  83.                         if (h.x < 1 || h.y < 1 || h.x > m || h.y > n) continue;
  84.  
  85.                         if (a[h.x][h.y] >= k) {
  86.                             Union(getIndex(i, j), getIndex(h.x, h.y));
  87.                         }
  88.                     }
  89.                 }
  90.             }
  91.  
  92.  
  93.             for (int i = 1; i <= m; i += 1) {
  94.                 for (int j = 1; j <= n; j += 1) {
  95.                     if (a[i][j] >= k) {
  96.                         cnt.insert(Find(getIndex(i, j)));
  97.                     }
  98.                 }
  99.             }
  100.  
  101.             res = max(res, (int)cnt.size());
  102.         }
  103.     }
  104.  
  105.     cout << res;
  106.  
  107.     return 0;
  108. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Hp1ysl
language:
C++14 (gcc 8.3)
created:
4 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!