| Time Limit: 1000MS |
|
Memory Limit: 65536K |
| Total Submissions: 16202 |
|
Accepted: 4349 |
Description
Given a
M×
N matrix
A.
A
ij ∈ {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 is
M,
N (
M ≤ 16,
N ≤ 300). The next
M lines every line contains
N 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
#include
#include
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; }