Advertisement
Josif_tepe

Untitled

Feb 3rd, 2025
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.63 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6. int main(){
  7.     int n, m;
  8.     cin >> n >> m;
  9.    
  10.     int mat[n][m];
  11.    
  12.     vector<pair<int, pair<int, int>>> v;
  13.     for(int i = 0; i < n; i++) {
  14.         for(int j = 0; j < m; j++) {
  15.             cin >> mat[i][j];
  16.            
  17.             v.push_back(make_pair(mat[i][j], make_pair(i, j)));
  18.         }
  19.     }
  20.    
  21.     sort(v.begin(), v.end());
  22.    
  23.     int res = 0;
  24.     int di[] = {-1, 1, 0, 0};
  25.     int dj[] = {0, 0, -1, 1};
  26.     vector<vector<bool>> visited(n, vector<bool>(m, false));
  27.     for(int i = 0; i < v.size(); i++) {
  28.         int si = v[i].second.first;
  29.         int sj = v[i].second.second;
  30.        
  31.         if(!visited[si][sj]) {
  32.             res++;
  33.  
  34.             visited[si][sj] = true;
  35.            
  36.             queue<int> q;
  37.             q.push(si);
  38.             q.push(sj);
  39.            
  40.             while(!q.empty()) {
  41.                 int ci = q.front();
  42.                 q.pop();
  43.                 int cj = q.front();
  44.                 q.pop();
  45.                
  46.                 for(int k = 0; k < 4; k++) {
  47.                     int ti = ci + di[k];
  48.                     int tj = cj + dj[k];
  49.                    
  50.                     if(ti >= 0 and ti < n and tj >= 0 and tj < m and !visited[ti][tj] and mat[ci][cj] <= mat[ti][tj]) {
  51.                         q.push(ti);
  52.                         q.push(tj);
  53.                         visited[ti][tj] = true;
  54.                     }
  55.                 }
  56.                
  57.             }
  58.         }
  59.        
  60.        
  61.        
  62.     }
  63.     cout << res << endl;
  64.  
  65.     return 0;
  66. }
  67.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement