2570번: 비숍2

https://www.acmicpc.net/problem/2570

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int n, m, map[100][100], rev[10001];
bool ck[10001];
vector<int> adj[10001];
bool dfs(int h) {
    if (ck[h]) return false;
    ck[h] = true;
    for (auto t : adj[h]) {
        if (!rev[t] || dfs(rev[t])) {
            rev[t] = h;
            return true;
        }
    }
    return false;
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        map[a - 1][b - 1] = -1;
    }
    bool flag = false;
    int cnt = 0, cnt2 = 0;
    for (int i = 0; i < 2 * n - 1; i++) {
        for (int j = 0; j < n; j++) {
            int x = i - j, y = j;
            if (x < 0 || y < 0 || x >= n || y >= n || map[x][y] == -1) {
                flag = false;
                continue;
            }
            if (!flag) flag = true, cnt++;
            map[x][y] = cnt;
        }
    }
    flag = false;
    for (int i = n - 1; i >= -n + 1; i--) {
        for (int j = 0; j < n; j++) {
            int x = i + j, y = j;
            if (x < 0 || y < 0 || x >= n || y >= n || map[x][y] == -1) {
                flag = false;
                continue;
            }
            if (!flag) flag = true, cnt2++;
            adj[map[x][y]].push_back(cnt2);
        }
    }
    int res = 0;
    for (int i = 1; i <= cnt; i++) {
        fill(ck + 1, ck + 1 + cnt, false);
        if (dfs(i)) res++;
    }
    printf("%d", res);
    return 0;
}