题目描述

给定一个N行M列的棋盘，已知某些格子禁止放置。

问棋盘上最多能放多少个不能互相攻击的車。

車放在格子里，攻击范围与中国象棋的“車”一致。

输入格式
第一行包含三个整数N,M,T，其中T表示禁止放置的格子的数量。

接下来T行每行包含两个整数x和y，表示位于第x行第y列的格子禁止放置，行列数从1开始。

输出格式
输出一个整数，表示结果。

数据范围
1≤N,M≤200

样例

输入样例：
8 8 0
输出样例：
8

算法1

(二部图)

遍历每一行，use数组是每一次都要初始化为0的，为1时表示当前列已经使用过了
数组c 记录的是每一列所放的车的所在行，例如，c[2]=3,表示第3行第2列放有车
flag[i][j]为true时，表示当前点不能放车子
整道题的思路就是去遍历每一行，再遍历当前列，如果这个位置可以放棋子，且这个位置还没有放过，则将use标记为1
表示已经遍历过这个位置了，然后在看看这一列会不会受到其他车子的攻击，如果有，则去找那一列，如果可以改变那一列
则去改变它，并且将棋子放在当前列，如何不能改变前面的车子，则试试其他列是否可以放车子

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
int N,M,t;
int a,b;
bool flag[210][210];
int c[210];
bool use[210];
int sum=0;
bool find(int x){
    for(int j=1;j<=M;j++){
        if( !flag[x][j] && use[j]==0){
            use[j]=1;
            if(c[j]==0 || find(c[j])){
                c[j]=x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    cin>>N>>M>>t;
    for(int i=0;i<t;i++){
        cin>>a>>b;
        flag[a][b]=true;
    }
    for(int i=1;i<=N;i++){
        if(find(i)){
            memset(use ,0 ,sizeof use);
            sum++;
        }
    }
    cout<<sum<<endl;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla