Submission #1247954

#TimeUsernameProblemLanguageResultExecution timeMemory
1247954dfhdfhdsfSelotejp (COCI20_selotejp)C++20
0 / 110
0 ms580 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; const int MAXX = MAXN * 10; // Số đoạn ngang tối đa const int MAXY = MAXN * 10; // Số đoạn dọc tối đa int n, m; string a[MAXN]; int idX[MAXN][15]; // ID đoạn ngang int idY[MAXN][15]; // ID đoạn dọc vector<int> adj[MAXX]; // adj[u] = các v bên Y mà u nối tới int matchY[MAXY]; bool vis[MAXX]; bool dfs(int u) { if (vis[u]) return false; vis[u] = true; for (int v : adj[u]) { if (matchY[v] == -1 || dfs(matchY[v])) { matchY[v] = u; return true; } } return false; } int run() { cin >> n >> m; for (int i = 0; i < n; ++i) cin >> a[i]; int cntSharp = 0; int xCount = 0; for (int i = 0; i < n; ++i) { int j = 0; while (j < m) { if (a[i][j] == '#') { ++xCount; while (j < m && a[i][j] == '#') { idX[i][j] = xCount; ++cntSharp; ++j; } } else { ++j; } } } int yCount = 0; for (int j = 0; j < m; ++j) { int i = 0; while (i < n) { if (a[i][j] == '#') { ++yCount; while (i < n && a[i][j] == '#') { idY[i][j] = yCount; ++i; } } else { ++i; } } } for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (a[i][j] == '#') { int u = idX[i][j]; int v = idY[i][j]; adj[u].push_back(v); } int match = 0; memset(matchY, -1, sizeof matchY); for (int u = 1; u <= xCount; ++u) { memset(vis, 0, sizeof vis); if (dfs(u)) ++match; } int res = cntSharp - xCount - yCount + match; cout << res << "\n"; return 0; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); return run(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...