378. Knight placement

Given a N×M The chessboard of , There are some squares where chess pieces are forbidden .

Ask the maximum number of knights that can't attack each other on the chessboard （ Chess “ The knight ”, Similar to Chinese chess “ Horse ”, according to “ Japan ” Word attack , But there is no Chinese chess “ Don't be a horse leg ” The rules of ）.

Input format

The first line contains three integers N,M,T, among T Indicates the number of cells that cannot be placed .

Next T Each line contains two integers x and y, It means to be in the second place x Xing di y Columns are not allowed to be placed in the grid , The number of rows and columns ranges from 1 Start .

Output format

Output an integer to represent the result .

Data range

1≤N,M≤100

sample input ：

2 3 0

sample output ：

4

Code ：

/*  The largest independent set   Select the most points   So that there is no edge between the selected points   In a bipartite graph   in total n A little bit   Find the maximum independent set n-m( The bigger the better ) Then remove the number of points m The smaller the better.  <=>  Remove the least points (m individual ), Break all edges  <=>  Find the minimum point to cover all m side  <=>  Find the largest match m */
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;

int n, m, k;
PII match[N][N];
bool g[N][N], st[N][N];

int dx[8] = {
    -2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {
    1, 2, 2, 1, -1, -2, -2, -1};

bool find(int x, int y)
{
    
    for (int i = 0; i < 8; i++)
    {
    
        int a = x + dx[i], b = y + dy[i];
        if (a < 1 || a > n || b < 1 || b > m)
            continue;

        if (g[a][b] || st[a][b])
            continue;

        st[a][b] = 1;

        PII t = match[a][b];
        if (t.first == 0 || find(t.first, t.second))
        {
    
            match[a][b] = {
    x, y};
            return true;
        }
    }

    return false;
}
int main()
{
    
    cin >> n >> m >> k;

    for (int i = 0; i < k; i++)
    {
    
        int x, y;
        cin >> x >> y;
        g[x][y] = true;
    }

    int res = 0;

    for (int i = 1; i <= n; i++)
    {
    
        for (int j = 1; j <= m; j++)
        {
    
            if ((i + j) % 2 || g[i][j])
                continue;
            memset(st, 0, sizeof st);
            if (find(i, j))
                res++;
        }
    }

    cout << n * m - k - res << endl;

    return 0;
}