Advertisement
Josif_tepe

Untitled

Jun 1st, 2024
622
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 <algorithm>
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     int n, m;
  9.     cin >> n >> m;
  10.     int mat[n][m];
  11.     vector<pair<int, pair<int, int>>> v;
  12.     for(int i = 0; i < n; i++) {
  13.         for(int j = 0; j < m; j++) {
  14.             cin >> mat[i][j];
  15.             v.push_back(make_pair(mat[i][j], make_pair(i, j)));
  16.         }
  17.     }
  18.     sort(v.begin(), v.end());
  19.     bool visited[n][m];
  20.     for(int i = 0; i < n; i++) {
  21.         for(int j = 0; j < m; j++) {
  22.             visited[i][j] = false;
  23.         }
  24.     }
  25.     int di[] = {-1, 1, 0, 0};
  26.     int dj[] = {0, 0, -1, 1};
  27.     int robotcinja = 0;
  28.  
  29.     for(int i = 0; i < v.size(); i++) {
  30.         int x = v[i].second.first;
  31.         int y = v[i].second.second;
  32.         if(!visited[x][y]) {
  33.             queue<int> q;
  34.             q.push(x);
  35.             q.push(y);
  36.  
  37.             visited[x][y] = true;
  38.             robotcinja++;
  39.             while(!q.empty()) {
  40.                 int ci = q.front();
  41.                 q.pop();
  42.                 int cj = q.front();
  43.                 q.pop();
  44.  
  45.                 for(int k = 0; k < 4; k++) {
  46.                     int ti = ci + di[k];
  47.                     int tj = cj + dj[k];
  48.                     if(ti >= 0 and ti < n and tj >= 0 and tj < m and !visited[ti][tj]) {
  49.                         if(mat[ci][cj] <= mat[ti][tj]) {
  50.                             q.push(ti);
  51.                             q.push(tj);
  52.                             visited[ti][tj] = true;
  53.                         }
  54.                     }
  55.                 }
  56.  
  57.  
  58.             }
  59.         }
  60.     }
  61. cout << robotcinja << endl;
  62.     return 0;
  63. }
  64.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement