糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

POJ 3740 Easy Finding 剪枝+位操作

题目大意:
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.


代码写得不好看,速度一般,200+ms
#include <stdio.h>
#include 
<string.h>

int M, N, T;
unsigned 
short arr[320];

int dfs(int idx, unsigned short ban, unsigned short sel)
{
    
int i;
    unsigned 
short mask;

    
if (idx == N)
        
return 1;

    mask 
= sel & arr[idx];
    
if (mask & (mask - 1))
        
return 0;
    
if (mask)
        
return dfs(idx + 1, (ban | arr[idx]) & ~mask, sel);

    
for (i = 0; i < M; i++{
        mask 
= 1 << i;
        
if (ban & mask)
            
continue;
        
if (!(arr[idx] & mask))
            
continue;
        
if (dfs(idx + 1, (ban | arr[idx]) & ~mask, sel | mask))
            
return 1;
    }


    
return 0;
}


int main()
{
    
int i, n, m;

    freopen(
"e:\\test\\in.txt""r", stdin);

    
while (scanf("%d%d"&M, &N) != EOF) {
        memset(arr, 
0, N*2);
        
for (m = 0; m < M; m++{
            
for (n = 0; n < N; n++{
                scanf(
"%d"&i);
                
if (i)
                    arr[n] 
|= 1 << m;
            }

        }

        printf(dfs(
000? "Yes, I found it\n" : "It is impossible\n");
    }


    
return 0;
}

posted on 2010-02-14 16:23 糯米 阅读(259) 评论(0)  编辑 收藏 引用 所属分类: POJ


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理