首页 > 代码库 > [ACM] POJ 3740 Easy Finding (DFS)
[ACM] POJ 3740 Easy Finding (DFS)
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 16202 | Accepted: 4349 |
Description
Given a M×N matrix A. Aij ∈ {0, 1} (0 ≤ i < M, 0 ≤ j < N), could you find some rows that let every cloumn contains and only contains one 1.
Input
There are multiple cases ended by EOF. Test case up to 500.The first line of input isM, N (M ≤ 16, N ≤ 300). The next M lines every line containsN integers separated by space.
Output
For each test case, if you could find it output "Yes, I found it", otherwise output "It is impossible" per line.
Sample Input
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
Sample Output
Yes, I found it It is impossible
Source
POJ Monthly Contest - 2009.08.23, MasterLuo
题意为:给定由01构成的矩阵,问能不能选出几行构成新矩阵,使得新矩阵每列有且只有一个1.
枚举所有行,行号递增,判断每行是否可以选(是否与前面所选的行发生冲突),当前行可选时,第j列如果为1,则用vis[j]=1标记,当行号>n(行数)时,判断每列是否都有1.
#include <iostream> #include <stdio.h> #include <string.h> const int maxn=18; const int maxm=310; int mp[maxn][maxm]; bool vis[maxm]; int n,m; bool yes; using namespace std; bool row_ok(int rth)//rth为行号,判断第rth行可以选 { for(int j=1;j<=m;++j) if(vis[j]&&mp[rth][j])//第j列已经有1了 return false; for(int j=1;j<=m;++j)//可以选 if(mp[rth][j]) vis[j]=true; return true; } bool judge()//当选的行号大于n时,判断一下是不是每列都有1 { for(int j=1;j<=m;++j) if(!vis[j]) return false; return true; } void dfs(int rth) { if(rth>n+1)//因为当rth=n+1时,还需要判断judge() return; if(judge())//注意这两个if { yes=1; return; } for(int i=rth;i<=n&&!yes;++i) { if(row_ok(i)) { dfs(i+1);//注意这里不是dfs(step+1),选的行号是递增的 for(int j=1;j<=m;++j)//还原 if(mp[i][j]) vis[j]=0; } } } int main() { while(scanf("%d%d",&n,&m)!=EOF) { for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&mp[i][j]); memset(vis,0,sizeof(vis)); yes=0; dfs(1); if(yes) printf("Yes, I found it\n"); if(!yes) printf("It is impossible\n"); } return 0; }
[ACM] POJ 3740 Easy Finding (DFS)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。