算法分析

最大独立集：选出最多的点使得选出的点之间没有边
在二分图中，求最大独立集 n - m
< == > 去掉最少的点，将所有边都破坏掉
< == > 找最小的点覆盖 m
< == > 找最大匹配 m

最大匹配数 = 最小点覆盖 = 总点数 - 最大独立集

两个格子的马若能互相攻击，则这两个格子能连上一条边，与棋盘覆盖 的题目相似，若两只马能够互相攻击则两只马的格子一定是两种类型的格子，如下图所示，选出最多个格子，使得选出的格子之间没有边，即求最大独立集问题

时间复杂度

参考文献

算法提高课

Java 代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 110;
    static int n,m,cnt;
    static boolean[][] g = new boolean[N][N];
    static boolean[][] st = new boolean[N][N];
    static Pair[][] match = new Pair[N][N];
    static int[] dx = new int[] {-2, -1, 1, 2, 2, 1, -1, -2};
    static int[] dy = new int[] {1, 2, 2, 1, -1, -2, -2, -1};
    static boolean find(int x,int y)
    {
        for(int i = 0;i < 8;i ++)
        {
            int a = x + dx[i];
            int b = y + dy[i];
            if(a <= 0 || a > n || b <= 0 || b > m) continue;
            if(st[a][b] || g[a][b]) continue;

            st[a][b] = true;
            Pair t = match[a][b];
            if(t.x == 0 || find(t.x,t.y))
            {
                t.x = x;
                t.y = y;
                return true;
            }
        }
        return false;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        cnt = scan.nextInt();//不能使用的格子
        for(int i = 0;i < cnt;i ++)
        {
            int a = scan.nextInt();
            int b = scan.nextInt();
            g[a][b] = true;
        }

        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
                match[i][j] = new Pair(0,0);

        int res = 0;
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
            {
                if((i + j) % 2 == 0 && !g[i][j])
                {
                    for(int k = 1;k <= n;k ++) Arrays.fill(st[k], false);
                    if(find(i,j)) res ++;
                }
            }

        System.out.println(n * m - cnt - res);
    }
}
class Pair
{
    int x,y;
    Pair(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
}