问题：

n * m的矩阵，有一些障碍点，用12的骨牌覆盖所有非障碍点 (12骨牌可重叠，骨牌可越界，骨牌可延伸到障碍点) 问最少需要 多少个。

题解：

在这里插入图片描述
• 尽量用一个骨牌覆盖两个格子，覆盖不了了再重叠使用骨牌
• 用和上一个题一样的方式求一个最大匹配，那么就有（2 * 最大匹配）个点已经被覆盖了
• 剩下了（总格子数-2 * 最大匹配）个点，每个点都需要一个骨牌
• 所以需要总格子数-2 * 最大匹配+最大匹配 = 总格子-最大匹配个骨牌
• 一个结论：
• 最小路径覆盖 （选最少的边覆盖掉所有的点）= 总顶点数-最大匹配数
（目前代码wa，但是还没找到哪里错了，基本思路是对的）

代码：

#include<iostream>
#include<cstring>
using namespace std;

const int maxn=800;
int a[maxn][maxn];
int n,m;
int vis[maxn];
int link[maxn]; 
int lx,ly;
char c[maxn][maxn];
int maxmatch(int x)
{
    for(int i=1;i<=n*m;i++)
    {    
            //if((i+j)%2==1)
            {
        //        if(i%2==1)continue;
                int y=i;
                if(!a[x][y]||vis[y])continue;
                vis[y]=1;
                if(link[y]==0||maxmatch(link[y]))
                {
                    link[y]=x;
                    return 1;
                }
            }

    }
    return 0;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        memset(link,0,sizeof(link));
        memset(a,0,sizeof(a));
        memset(c,'0',sizeof(c));
        char ch=getchar();
        int tot=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>c[i][j];
            }
            char ch=getchar();
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(c[i][j]=='*')
                {
                    if(c[i-1][j]=='*')
                        a[(i-2)*m+j][(i-1)*m+j]=a[(i-1)*m+j][(i-2)*m+j]=1;
                    if(c[i+1][j]=='*')
                        a[(i)*m+j][(i-1)*m+j]=a[(i-1)*j+j][(i)*m+j]=1;
                    if(c[i][j-1]=='*')
                        a[(i-1)*m+j-1][(i-1)*m+j]=a[(i-1)*j+j][(i-1)*m+j-1]=1;
                    if(c[i][j+1]=='*')
                        a[(i-1)*m+j+1][(i-1)*m+j]=a[(i-1)*j+j][(i-1)*m+j+1]=1;

                    tot++;
                }
            }
         } 
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                int x=(i-1)*m+j;
                if((i+j)%2==0&&c[i][j]=='*')
                {
                    memset(vis,0,sizeof(vis));
                    sum+=maxmatch(x);
                }
            //    if(i%2==0)continue;

            }

        }
    //    printf("tot=%d\n",tot);
    //    printf("sum=%d\n",sum);
        printf("%d\n",tot-sum);
    }
    return 0;
}