Hopcroft-Karp TLE

#include <bits/stdc++.h>

class Matching {
public:
  size_t left_;
  size_t right_;
  std::vector <int> que_;
  std::vector <int> distance_;
  std::vector <int> match_left_;
  std::vector <int> match_right_;
  std::vector <std::vector <int>> adj_;

  Matching(size_t left, size_t right)
  : left_(left),
    right_(right),
    que_(left),
    adj_(left),
    distance_(left),
    match_left_(left, -1),
    match_right_(right, -1) {
  }

  void AddEdge(int from, int to) {
    adj_[from].push_back(to);
  }

  void Bfs() {
    unsigned que_size_ = 0;
    for (size_t i = 0; i < left_; ++i) {
      if (match_left_[i] != -1) {
        distance_[i] = -1;
      } else {
        distance_[i] = 0;
        que_[que_size_++] = static_cast <int>(i);
      }
    }

    unsigned que_ptr = 0;
    while (que_ptr < que_size_) {
      int node = que_[que_ptr++];
      for (const int& to : adj_[node]) {
        if (match_right_[to] != -1
        && distance_[match_right_[to]] == -1) {
          que_[que_size_++] = match_right_[to];
          distance_[match_right_[to]] = distance_[node] + 1;
        }
      }
    }
  }

  bool Dfs(int node) {
    for (const int& to : adj_[node]) {
      if (match_right_[to] == -1) {
        match_left_[node] = to;
        match_right_[to] = node;
        return true;
      }
    }

    for (const int& to : adj_[node]) {
      if (distance_[match_right_[to]] == distance_[node] + 1
      && Dfs(match_right_[to])) {
        match_left_[node] = to;
        match_right_[to] = node;
        return true;
      }
    }

    return false;
  }

  int HopcroftKarp() {
    int matching = 0;
    int augment = 1;

    while (augment > 0) {
      Bfs();
      augment = 0;
      for (size_t i = 0; i < left_; ++i) {
        if (match_left_[i] == -1) {
          augment += Dfs(static_cast <int>(i));
        }
      }
      matching += augment;
    }

    return matching;
  }
};

using namespace std;

void RunCase() {
  int n, m, a, b;
  cin >> n >> m >> a >> b;

  vector <vector <char>> grid(n, vector <char>(m));
  for (auto& row : grid) {
    for (auto& c : row) {
      cin >> c;
    }
  }

  int vacant = 0;
  for (const auto& row : grid) {
    for (const auto& c : row) {
      vacant += (c == '*');
    }
  }

  if (vacant == 0) {
    cout << "0\n";
    return;
  }

  if (2 * b <= a) {
    cout << vacant * b * 2 << "\n";
    return;
  }

  const int grid_size = n * m;
  Matching matching(grid_size / 2 + grid_size % 2, grid_size / 2);

  constexpr int dx[] = {-1, 0, 0, 1};
  constexpr int dy[] = {0, -1, 1, 0};

  vector <int> code(n * m);
  for (int i = 2; i < n * m; ++i) {
    code[i] = code[i - 2] + 1;
  }

  for (int i = 0; i < n; ++i) {
    for (int j = i % 2; j < m; j += 2) {
      if (grid[i][j] == '.') {
        continue;
      }

      for (size_t k = 0; k < 4; ++k) {
        int new_i = i + dx[k];
        int new_j = j + dy[k];
        if (0 <= new_i && new_i <= n - 1
            && 0 <= new_j && new_j <= m - 1
            && grid[new_i][new_j] != '.') {
          matching.AddEdge(code[i * m + j], code[new_i * m + new_j]);
        }
      }
    }
  }

  int mat = matching.HopcroftKarp();
  assert(mat * 2 <= vacant);
  cout << mat * a + b * (vacant - 2 * mat) << "\n";
}


int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int tt = 1;
  //std::cin >> tt;
  while (tt--) {
    RunCase();
  }
  return 0;
}