Advertisement
Josif_tepe

Untitled

Oct 24th, 2021
136
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.55 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5. typedef long long ll;
  6.  
  7. int main()
  8. {
  9.     int n, m;
  10.     cin >> n >> m;
  11.     char mat[n][m];
  12.     for(int i = 0; i < n; i++) {
  13.         for(int j = 0; j < m; j++) {
  14.             cin >> mat[i][j];
  15.         }
  16.     }
  17.     bool visited[n][m];
  18.     for(int i = 0; i < n; i++) {
  19.         for(int j = 0; j < m; j++) {
  20.             visited[i][j] = false;
  21.         }
  22.     }
  23.     int ovci = 0, volci = 0;
  24.     for(int i = 0; i < n; i++) {
  25.         for(int j = 0; j < m; j++) {
  26.             if(mat[i][j] != '#' and !visited[i][j]) {
  27.                 queue<int> Q;
  28.                 Q.push(i);
  29.                 Q.push(j);
  30.                 visited[i][j] = true;
  31.                 int kolku_ovci = 0;
  32.                 int kolku_volci = 0;
  33.                 while(!Q.empty()) {
  34.                     int ci = Q.front();
  35.                     Q.pop();
  36.                     int cj = Q.front();
  37.                     Q.pop();
  38.                     if(mat[ci][cj] == 'o') {
  39.                         kolku_ovci++;
  40.                     }
  41.                     if(mat[ci][cj] == 'v') {
  42.                         kolku_volci++;
  43.                     }
  44.                    
  45.                     if(ci + 1 < n and mat[ci + 1][cj] != '#' and !visited[ci + 1][cj]) {
  46.                         Q.push(ci + 1);
  47.                         Q.push(cj);
  48.                         visited[ci + 1][cj] = true;
  49.                     }
  50.                     if(ci - 1 >= 0 and mat[ci - 1][cj] != '#' and !visited[ci - 1][cj]) {
  51.                         Q.push(ci - 1);
  52.                         Q.push(cj);
  53.                         visited[ci - 1][cj] = true;
  54.                     }
  55.                     if(cj + 1 < m and mat[ci][cj + 1] != '#' and !visited[ci][cj + 1]) {
  56.                         Q.push(ci);
  57.                         Q.push(cj + 1);
  58.                         visited[ci][cj + 1] = true;
  59.                     }
  60.                     if(cj - 1 >= 0 and mat[ci][cj - 1] != '#' and !visited[ci][cj - 1]) {
  61.                         Q.push(ci);
  62.                         Q.push(cj - 1);
  63.                         visited[ci][cj - 1] = true;
  64.                     }
  65.                 }
  66.                 if(kolku_ovci > kolku_volci) {
  67.                     ovci += kolku_ovci;
  68.                 }
  69.                 else {
  70.                     volci += kolku_volci;
  71.                 }
  72.             }
  73.         }
  74.     }
  75.     cout << ovci << " " << volci << endl;
  76.     return 0;
  77. }
  78. /*
  79.  8 8
  80.  .######.
  81.  #..o...#
  82.  #.####.#
  83.  #.#v.#.#
  84.  #.#.o#o#
  85.  #o.##..#
  86.  #.v..v.#
  87.  .######.
  88.  **/
  89.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement