제출 #1247954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247954		dfhdfhdsf	Selotejp (COCI20_selotejp)	C++20	0 / 110	0 ms	580 KiB

Main

#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();
}

• Subtask 1: 0 / 35
• Subtask 2: 0 / 35
• Subtask 3: 0 / 40