比赛(Test):查看题目 Show Problem
赛题题目:监考老师
所属比赛:第3次期中风波模拟赛
问题编号:359 [提交该赛题]
描述: 【问题背景】
某日，浪子被叫去了……
【问题描述】
马上就要期中考试了，自然，在每个考场都要放监考老师（相信如果没有监考老师浪子等人会很高兴的），但是这些监考老师非常严格（谁知道是哪位“仁君”训练出来的）而且只看前后、左右，别的地方都不管——而且能透过学生看学生另一边的学生（即如果老师站在教室第X排第Y个时，他只能看到第X排学生和每排第Y个学生的考试情况——即是否在作弊）。但是学校为了节省教室，所以把很多的学生聚集在一起考试（^_^||），而且这些老师非常懒——他们不会站着，只会坐到那些空位子上去。
为了控制整个考场，所以必须多放些监考老师（这个学校师资不错），但监考老师一旦发现某人在东张西望（当然，他自己也在东张西望），就会把那家伙拖出去（好可怜啊T_T）。为了不引起混乱（监考老师把监考老师拖出去）所以每行每列最多只能放一个监考老师。
于是校长向浪子卑躬屈膝，为的只是求每个考场内最多能放多少个监考老师。
输入格式: 第一行，两个数N，M分别表示考场有N排，每排M个人（0≤N，M≤200）。
接下来一个N*M的矩阵，0表示有学生坐着，1表示没有学生坐着。监考老师只能坐那些没有学生坐着的地方。
输出格式: 一个数，在这个考场里最多能放多少个监考老师。
输入文件: 直接输入即可
输出文件: 直接输出即可 注意,不要在最后输出空行或空格!
样例输入:
5 5
0 0 0 1 0
0 1 0 0 0
1 0 0 0 0
0 0 1 0 0
0 0 0 0 1
样例输出: 5
【样例说明】
五个老师刚好坐在（1，4）、（2，2）、（3，1）、（4，3）、（5，5），能够监视整个考场，并且不会引起老师们的混乱
*/
#include<iostream>
using namespace std；
int m,n,k；
int empty[200][200]；
bool x[200],y[200]；
struct points
{
int x；
int y；
} emps[40000]；
int dp[40000]；
int dfs_try(int dep,int c){
if (dep==k){
if (dp[dep]<c) dp[dep]=c；
return dp[dep]；
}
if (dp[dep]!=-1) return dp[dep]；
if (!x[emps[dep].x]&&!y[emps[dep].y]){
x[emps[dep].x]=y[emps[dep].y]=true；
dp[dep]=max(dp[dep],dfs_try(dep+1,c+1))；
x[emps[dep].x]=y[emps[dep].y]=false；
}
dp[dep]=max(dp[dep],dfs_try(dep+1,c))；
return dp[dep]；
}
int main (void){
cin>>m>>n；
k=0；
for (int i=0；i<m；++i)
for (int j=0；j<n；++j){
cin>>empty[i][j]；
if (empty[i][j]){
emps[k].x=i；
emps[k].y=j；
dp[k]=-1；
++k；
}
}
dp[k]=0；
for (int i=0；i<m；++i) x[i]=false；
for (int i=0；i<n；++i) y[i]=false；
cout<<dfs_try(0,0)；
// while (1)；
return 0；
}