fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3.  
  4. using namespace std;
  5. const int arr = 1e3 + 10;
  6. int dr[8] = {0, -1, -1, -1, 0, 1, 1, 1};
  7. int dc[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
  8. int n, m;
  9. bool vis[arr][arr];
  10. int h[arr][arr];
  11.  
  12. void read(){
  13.     cin >> n >> m;
  14.     for(int i = 1; i <= n; ++i){
  15.         for(int j = 1; j <= m; ++j){
  16.             cin >> h[i][j];
  17.         }
  18.     }
  19. }
  20.  
  21. bool valid(int r, int c){
  22.     return (r > 0 && c > 0 && r <= n && c <= m);
  23. }
  24.  
  25. int dfs(int r, int c){
  26.     vis[r][c] = 1;
  27.     int res = 0;
  28.     for(int i = 0; i < 8; ++i){
  29.         int nxt_r = r + dr[i];
  30.         int nxt_c = c + dc[i];
  31.         if(valid(nxt_r, nxt_c)){
  32.             if(h[nxt_r][nxt_c] == h[r][c] && !vis[nxt_r][nxt_c]){
  33.                 res += dfs(nxt_r, nxt_c);
  34.             }
  35.             else if(h[nxt_r][nxt_c] > h[r][c]) res++;
  36.         }
  37.     }
  38.     return res;
  39. }
  40.  
  41. int bfs(int r, int c){
  42.     vis[r][c] = 1;
  43.     queue<pair<int, int>> q;
  44.     q.push({r, c});
  45.     int higher = 0;
  46.     while(!q.empty()){
  47.         int r = q.front().first;
  48.         int c = q.front().second;
  49.         q.pop();
  50.         for(int i = 0; i < 8; ++i){
  51.             int nxt_r = r + dr[i];
  52.             int nxt_c = c + dc[i];
  53.             if(valid(nxt_r, nxt_c)){
  54.                 if(h[nxt_r][nxt_c] > h[r][c]){
  55.                     higher++;
  56.                 }
  57.                 else if(h[nxt_r][nxt_c] == h[r][c] && !vis[nxt_r][nxt_c]){
  58.                     q.push({nxt_r, nxt_c});
  59.                     vis[nxt_r][nxt_c] = 1;
  60.                 }
  61.             }
  62.         }
  63.     }
  64.     return higher;
  65. }
  66.  
  67. void solve(){
  68.     int ans = 0;
  69.     for(int i = 1; i <= n; ++i){
  70.         for(int j = 1; j <= m; ++j){
  71.             if(!vis[i][j]){
  72.                 int higher = bfs(i, j);
  73.                 if(higher == 0) ans++;
  74.             }
  75.         }
  76.     }
  77.     cout << ans;
  78. }
  79.  
  80. int main()
  81. {
  82.     read();
  83.     solve();
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/381dT9
language:
C++14 (clang 8.0)
created:
6 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!