Advertisement
Josif_tepe

Untitled

May 11th, 2021
133
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.78 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <cmath>
  4. #include <algorithm>
  5. using namespace std;
  6. int main() {
  7.     int r, c;
  8.     cin >> r >> c;
  9.     int mat[55][55];
  10.     for (int i = 0; i < r; i++) {
  11.         for (int j = 0; j < c; j++) {
  12.             cin >> mat[i][j];
  13.         }
  14.     }
  15.     bool visited[55][55];
  16.     for (int i = 0; i < r; i++) {
  17.         for (int j = 0; j < c; j++) {
  18.             visited[i][j] = false;
  19.         }
  20.     }
  21.     int min1 = 10000000;
  22.     queue<int> a;
  23.     int si;
  24.     int sj;
  25.     int roboti = 0;
  26.     for (int x = 0; x < r * c; x++) {
  27.         si = -1;
  28.         sj = -1;
  29.         min1 = 10000000;
  30.         for (int i = 0; i < r; i++) {
  31.             for (int j = 0; j < c; j++) {
  32.                 if (min1 > mat[i][j] && !visited[i][j]) {
  33.                     min1 = min(mat[i][j], min1);
  34.                     si = i;
  35.                     sj = j;
  36.                 }
  37.             }
  38.         }
  39.         int di[4] = {1, -1, 0, 0};
  40.         int dj[4] = {0, 0, 1, -1};
  41.         if (si != -1) {
  42.             a.push(si);
  43.             a.push(sj);
  44.             roboti++;
  45.             visited[si][sj] = true;
  46.             while (!a.empty()) {
  47.                 int ci = a.front();
  48.                 a.pop();
  49.                 int cj = a.front();
  50.                 a.pop();
  51.                 for (int i = 0; i < 4; i++) {
  52.                     int tmpi = ci + di[i];
  53.                     int tmpj = cj + dj[i];
  54.                     if (tmpi >= 0 && tmpj >= 0 && tmpi < r && tmpj < c && !visited[tmpi][tmpj] &&
  55.                         mat[tmpi][tmpj] >= mat[ci][cj]) {
  56.                         a.push(tmpi);
  57.                         a.push(tmpj);
  58.                         visited[tmpi][tmpj] = true;
  59.                     }
  60.                 }
  61.             }
  62.         }
  63.     }
  64.     cout <<roboti;
  65. }
  66.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement