Advertisement
Josif_tepe

Untitled

Feb 20th, 2024
626
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.52 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <queue>
  4. #include <vector>
  5. using namespace std;
  6. const int maxn = 500;
  7. const int di[] = {-1, 1, 0, 0};
  8. const int dj[] = {0, 0, -1, 1};
  9. int n, m;
  10. char mat[maxn][maxn];
  11. bool visited[maxn][maxn];
  12. int wolves, sheep;
  13. void dfs(int i, int j) {
  14. //    cout << i << " " << j << endl;
  15.     visited[i][j] = true;
  16.    
  17.     if(mat[i][j] == 'v') {
  18.         wolves++;
  19.     }
  20.     if(mat[i][j] == 'o') {
  21.         sheep++;
  22.     }
  23.     for(int k = 0; k < 4; k++) {
  24.         int ti = i + di[k];
  25.         int tj = j + dj[k];
  26.        
  27.         if(ti >= 0 and ti < n and tj >= 0 and tj < m and !visited[ti][tj] and mat[ti][tj] != '#') {
  28.             dfs(ti, tj);
  29.         }
  30.     }
  31.    
  32. }
  33. int main() {
  34.     ios_base::sync_with_stdio(false);
  35.     cin >> n >> m;
  36.     for(int i = 0; i < n; i++) {
  37.         for(int j = 0; j < m; j++) {
  38.             cin >> mat[i][j];
  39.             visited[i][j] = false;
  40.         }
  41.     }
  42.     int res_sheep = 0, res_wolves = 0;
  43.    
  44.     for(int i = 0; i < n; i++) {
  45.         for(int j = 0; j < m; j++) {
  46.             if(mat[i][j] != '#' and !visited[i][j]) {
  47.                 wolves = 0;
  48.                 sheep = 0;
  49.                 dfs(i, j);
  50.                 if(sheep > wolves) {
  51.                     res_sheep += sheep;
  52.                 }
  53.                 else {
  54.                     res_wolves += wolves;
  55.                 }
  56.             }
  57.         }
  58.     }
  59.     cout << res_sheep << " " << res_wolves << endl;
  60.     return 0;
  61. }
  62. /*
  63.  6 6
  64.  1 2
  65.  2 3
  66.  2 5
  67.  3 5
  68.  3 4
  69.  5 6
  70.  **/
  71.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement