fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define dbg(x) cout << #x << " : " << x << endl
  5. #define rep(i, a, b) for (int i = (a); i <= (b); i++)
  6. #define inf 1000000000000000000
  7. priority_queue<ll, vector<ll>, greater<int>> qp;
  8. priority_queue<ll> qr;
  9. #define maxn 705
  10. #define mod 1000000007
  11. ll dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
  12. ll dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
  13. /**************TEMPLATES**********************/
  14. ll n, m;
  15. ll a[maxn][maxn], dau[maxn][maxn], res[maxn][maxn];
  16. struct node
  17. {
  18.     ll x, y;
  19. };
  20. bool check(ll fi, ll se)
  21. {
  22.     if (0 > fi || 0 > se || fi >= n || se >= m)
  23.         return true;
  24.     return false;
  25. }
  26. bool cmp(pair<ll,node> A, pair<ll,node> B){
  27.     if(A.first==B.first) return A.second.x>B.second.x;
  28.     return A.first>B.first;
  29. }
  30. vector<pair<ll, node>> vt;
  31. void dfs(node source)
  32. {
  33.     dau[source.x][source.y]=1;
  34.     for(ll i=0;i<8;i++){
  35.         node tmp;
  36.         tmp.x = source.x + dx[i];
  37.         tmp.y = source.y + dy[i];
  38.         if(check(tmp.x,tmp.y)) continue;
  39.         if(dau[tmp.x][tmp.y]==1) continue;
  40.         if(a[tmp.x][tmp.y]<=a[source.x][source.y]) dfs(tmp);
  41.     }
  42. }
  43. int main()
  44. {
  45.     // freopen("input.txt", "r", stdin);
  46.     // freopen("output.txt", "w", stdout);
  47.     cin >> n >> m;
  48.     ll i, j;
  49.     for (i = 0; i < n; i++)
  50.         for (j = 0; j < m; j++)
  51.         {
  52.             cin >> a[i][j];
  53.             node tmp;
  54.             tmp.x = i;
  55.             tmp.y = j;
  56.             vt.push_back({a[i][j], tmp});
  57.         }
  58.     sort(vt.begin(),vt.end(),cmp);
  59.     ll ans=0;
  60.     for(auto p: vt){
  61.         if(dau[p.second.x][p.second.y]==1) continue;
  62.         ans++;
  63.         node source;
  64.         source.x = p.second.x;
  65.         source.y = p.second.y;
  66.         dfs(source);
  67.     }
  68.     // cout<<1;
  69.     cout<<ans;
  70.     return 0;
  71. }
Success #stdin #stdout 0.01s 5364KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cw71pI
language:
C++14 (gcc 8.3)
created:
2 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!