Advertisement
Josif_tepe

Untitled

Apr 26th, 2021
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.09 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5. int main() {
  6.     int n, m;
  7.     cin >> n >> m;
  8.     char mat[n][m];
  9.     for(int i = 0; i < n; i++) {
  10.         for(int j = 0; j < m; j++) {
  11.             cin >> mat[i][j];
  12.         }
  13.     }
  14.     bool visited[n][m];
  15.     for(int i = 0; i < n; i++) {
  16.         for(int j = 0; j < m; j++) {
  17.             visited[i][j] = false;
  18.         }
  19.     }
  20.     int zivi_volci = 0;
  21.     int zivi_ovci = 0;
  22.     int di[] = {-1, 1, 0, 0};
  23.     int dj[] = {0, 0, -1, 1};
  24.    
  25.     for(int i = 0; i < n; i++) {
  26.         for(int j = 0; j < m; j++) {
  27.             if(mat[i][j] != '#' and !visited[i][j]) {
  28.                 queue<int> q;
  29.                 q.push(i);
  30.                 q.push(j);
  31.                 visited[i][j] = true;
  32.                 int ovci = 0, 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.                         ovci++;
  40.                     }
  41.                     if(mat[ci][cj] == 'v') {
  42.                         volci++;
  43.                     }
  44.                     for(int k = 0; k < 4; k++) {
  45.                         int ti = ci + di[k];
  46.                         int tj = cj + dj[k];
  47.                         if(ti >= 0 and ti < n and tj >= 0 and tj < m and !visited[ti][tj] and mat[ti][tj] != '#') {
  48.                             visited[ti][tj] = true;
  49.                             q.push(ti);
  50.                             q.push(tj);
  51.                         }
  52.                     }
  53.                 }
  54.                 if(volci >= ovci) {
  55.                     zivi_volci += volci;
  56.                 }
  57.                 else {
  58.                     zivi_ovci += ovci;
  59.                 }
  60.                
  61.             }
  62.         }
  63.     }
  64.     cout << zivi_ovci << " " << zivi_volci << endl;
  65.     return 0;
  66. }
  67.  
  68. /*
  69.  .######.
  70.  #..o...#
  71.  #.####.#
  72.  #.#v.#.#
  73.  #.#.o#o#
  74.  #o.##..#
  75.  #.v..v.#
  76.  .######.
  77.  
  78.  овци 3
  79.  волк 1
  80.  
  81.  
  82.  
  83.  ####
  84.  #ov#
  85.  ####
  86.  */
  87.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement