Untitled
unknown
plain_text
a month ago
2.1 kB
4
Indexable
#include <bits/stdc++.h> using namespace std; #define ll long long void Init() { ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); #ifdef CLION freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); freopen("error.txt", "w", stderr); #else // freopen("input.txt", "r", stdin); #endif } vector<pair<int, int> > adj1, adj2; vector<vector<int> > adj(50 * 50); vector<int> a(50 * 50, -1); int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; bool dfs(int u, vector<bool> &vis) { if (vis[u]) return false; vis[u] = true; for (int v: adj[u]) { if (a[v] == -1 || dfs(a[v], vis)) { a[v] = u; return true; } } return false; } void Mesh_JOO() { int n, m; cin >> n >> m; vector<vector<char> > grid(n + 1, vector<char>(m + 1)); vector<vector<int> > g(n + 1, vector<int>(m + 1)); int id = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> grid[i][j]; if (grid[i][j] == 'W') adj1.push_back({i, j}); else if (grid[i][j] == 'G') { adj2.push_back({i, j}); g[i][j] = id++; } } } id = 1; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (grid[i][j] == 'W') { for (int d = 0; d < 4; ++d) { int x = i + dx[d], y = j + dy[d]; if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 'G') { adj[id].push_back(g[x][y]); } } id += 1; } } } int ans = 0; for (int i = 1; i < id; ++i) { vector<bool> vis(50 * 50); ans += dfs(i, vis); } cout << ans << '\n'; } int main() { Init(); int t{1}; // cin >> t; while (t--) { Mesh_JOO(); } return 0; }
Editor is loading...
Leave a Comment