Advertisement
Anton_NNNNNNNNNNNN

Untitled

May 26th, 2022
665
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. int n, m, a, b;
  2. string c[110];
  3. pair <int, int> mt[110][110];
  4. int used[110][110];
  5.  
  6. vector <int> dx = {1, -1, 0, 0};
  7. vector <int> dy = {0, 0, 1, -1};
  8.  
  9. bool dfs(int x1, int y1, int t) {
  10.     if (used[x1][y1] == t)
  11.         return false;
  12.     used[x1][y1] = t;
  13.     for (int i = 0; i < 4; i++) {
  14.         int x2 = x1 + dx[i], y2 = y1 + dy[i];
  15.         if (x2 < 0 || y2 < 0 || x2 >= n || y2 >= m)
  16.             continue;
  17.         if (c[x2][y2] == '.')
  18.             continue;
  19.         if (mt[x2][y2] == make_pair(-1, -1) || dfs(mt[x2][y2].F, mt[x2][y2].S, t)) {
  20.             mt[x2][y2] = make_pair(x1, y1);
  21.             return true;
  22.         }
  23.     }
  24.     return false;
  25. }
  26.  
  27. int main() {
  28.     files("dominoes.in", "dominoes.out");
  29.  
  30.     cin >> n >> m >> a >> b;
  31.     for (int i = 0; i < n; i++)
  32.         cin >> c[i];
  33.  
  34.     for (int i = 0; i < n; i++)
  35.         for (int j = 0; j < m; j++)
  36.             mt[i][j] = make_pair(-1, -1);
  37.  
  38.     int now = 1, ans = 0, kol = 0;
  39.     for (int i = 0; i < n; i++)
  40.         for (int j = 0; j < m; j++)
  41.             if (c[i][j] == '*') {
  42.                 kol++;
  43.                 if ((i + j) % 2 == 0) {
  44.                     if (dfs(i, j, now))
  45.                         ans++;
  46.                     now++;
  47.                 }
  48.             }
  49.  
  50.     cout << min(ans * a + (kol - 2 * ans) * b, kol * b) << endl;
  51. }
Advertisement
RAW Paste Data Copied
Advertisement