首页 > 代码库 > AOj448有趣的矩阵

AOj448有趣的矩阵

2024-07-07 16:15:37   225人阅读

题目：http://icpc.ahu.edu.cn/OJ/Problem.aspx?id=448

这题刚开始想弄个2^16  的集合搞，然后位运算搞下。  位运算一直没搞好，不用又超时。 还是直接搜吧，加剪枝就过了。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <iostream>
using namespace std;
int Flag=0;
int vis[1000];
int n,m;
int gg[100][306];
void dfs(int x)
{
    if(Flag) return ;
    if(x==m){Flag=1;return ;}
    if(vis[x]) dfs(x+1);
    else{
        for(int i=0;i<n;i++){
            int hehe=0;
            int vis1[305];
            if(!gg[i][x]) continue;
            for(int j=0;j<m;j++)
                vis1[j]=vis[j];
            for(int j=0;j<m;j++){
                if(vis[j]&&gg[i][j]){hehe=1;break;}
            }
            if(!hehe){
                for(int j=0;j<m;j++){
                    if(gg[i][j]) vis[j]=1;
                }
                dfs(x+1);
                for(int j=0;j<m;j++)
                    vis[j]=vis1[j];
            }
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF){
        Flag=0;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            scanf("%d",&gg[i][j]);
        dfs(0);
        if(!Flag) printf("It is impossible\n");
        else printf("Yes, I found it\n");
    }
    return 0;
}

　　

 


联系
我们