http://acm.pku.edu.cn/JudgeOnline/problem?id=3740
這道題目要求：選出一些行使得這些行構(gòu)成矩陣的每一列都有且只有一個1。
1 #include<cstdio>
2 #include<string.h>
3 using namespace std;
4
5 int m,n,map[16][300];
6 bool used[300];
7 bool find;
8
9 bool match(){ //判斷所選取的行構(gòu)成的矩陣是否符合情況
10 for(int i = 0;i < n;++i){
11 if(!used[i])return false;
12 }
13 return true;
14 }
15
16 bool check(int row){
17 for(int i = 0;i < n;++i){
18 if(used[i] && map[row][i])return false; //used[i]&&map[row][i]表示該列有選取的該列有不只一個1，返回false放棄這種情況。
19 }
20 for(int i = 0;i < n;++i){
21 if(map[row][i]){
22 used[i] = true;
23 }
24 }
25 return true;
26 }
27
28 void dfs(int start){
29 if(start>m || find)return;
30 if(match()){
31 printf("Yes, I found it\n");
32 find = true;
33 return;
34 }
35 for(int i = start;i < m && !find;++i){
36 if(check(i)){
37 dfs(i+1);
38 for(int j = 0;j < n;++j){
39 if(map[i][j])used[j] = false;
40 }
41 }
42 }
43 }
44
45 int main()
46 {
47 int i,j;
48 while(scanf("%d%d",&m,&n)!=EOF){
49 for(i = 0;i < m;++i){
50 for(j = 0;j < n;++j){
51 scanf("%d",&map[i][j]);
52 }
53 }
54 memset(used,false,sizeof(used));
55 find = false;
56 dfs(0);
57 if(!find)printf("It is impossible\n");
58 }
59 return 0;
60 }
61