372. chessboard coverage

Given a N That's ok N A chessboard of columns , It is known that some grids are forbidden to place .

Find the maximum number of pieces that can be placed on the chessboard. The length is 2、 Width is 1 The dominoes of , The border of the dominoes coincides with the grid （ Dominoes occupy two squares ）, And any two dominoes don't overlap .

Input format

The first line contains two integers N and t, among t Is 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 , Show the result .

Data range

1≤N≤100,
0≤t≤100

sample input ：

8 0

sample output ：

32

Code ：

/*  Because each domino will only be matched by two consecutive squares , In the sum of rows and columns of the coordinates of the square , It must be a combination of even and odd numbers , That is, each blue square in the figure will only form a domino with the surrounding white squares , Each white square will only form a domino with the surrounding blue square , Find the maximum number of combinations , So the problem is the maximum matching problem of a bipartite graph   You only need the sum of the maximum matches of all the even squares , That is to say, even numbered squares are connected to odd numbered squares with a directed edge  */

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;

int n, m;
PII match[N][N];
bool g[N][N], st[N][N];
int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, 1, 0, -1};

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

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

    return false;
}

int main()
{
    
    cin >> n >> m;

    while (m--)
    {
    
        int x, y;
        cin >> x >> y;
        g[x][y] = true;
    }

    int res = 0;
    //  Can regard sum as odd as a boy 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if ((i + j) % 2 && !g[i][j])
            {
    
                memset(st, 0, sizeof st);
                if (find(i, j))
                    res++;
            }

    cout << res << endl;

    return 0;
}