stdKonjac's Blog

An AC a day keeps the WA away ~

【简单寻找】

题目描述

给一个 M 行 N 列的 01 矩阵,让你选出一些行(不一定选出全部行)使得每一列都有且只有一个 1。其中 M<=16,N<=300。

输入格式

输入含有多组数据。以文件结束符(Eof)为结束。最多会有 500 组。
输入之间会有梯度,也就是不是每组输入都是 500 组。
对每组数据,第一行:两个由空格隔开的整数 M 和 N。然后是 M 行每行 N 个等于 0 或者等于 1 的整数,整数之间由空格隔开。

输出格式

对每组数据输出一行,如果可以达到题中要求,输出“Yes”否则输出“No”。均不包括引号。

样例数据 1

输入

3 3
0 1 0
0 0 1
1 0 0
4 4
0 0 0 1
1 0 0 0
1 1 0 1
0 1 0 0

输出

Yes
No

直接枚举情况DFS即可,哎还是要多练搜索啊,太不熟练了……另外还可以用DLX写。

下面是代码:


下面是DLX写法,比不用DLX快3倍!
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.