首页 > 其他 > 详细

UVA 11205 The broken pedometer

时间:2015-04-16 07:53:36      阅读:235      评论:0      收藏:0      [点我收藏+]

只要用哪几列就可以使P行都不同。暴力DFS就可以了。

#include<stdio.h>
#include<string.h>
int n, p;//n列 p行
int map[105][20];
int flaglie[20];
char s[105][20];
int sum;
void sou(int ans)
{
    int i, c = 0, j, flag = 0;
    if (ans == n)
    {
        for (i = 0; i < p; i++)
        {
            c = 0;
            for (j = 0; j < n; j++)
            {
                if (flaglie[j] == 1)
                {
                    s[i][c] = map[i][j] + 0;
                    c++;
                }
            }
            s[i][c] = \0;
        }
        for (i = 0; i < p; i++)
        {
            for (j = i + 1; j < p; j++)
            {
                if (strcmp(s[i], s[j]) == 0)
                {
                    flag = 1;
                    break;
                }
            }
        }
        if (flag == 0) { if (c < sum)sum = c; }
        return;
    }
    flaglie[ans] = 1;
    sou(ans + 1);
    flaglie[ans] = 0;
    sou(ans + 1);
}
int main()
{
    int i, j, sb, bs;
    scanf("%d", &sb);
    for (bs = 0; bs < sb; bs++)
    {
        scanf("%d%d", &n, &p);
        sum = n;
        for (i = 0; i < p; i++)
        {
            for (j = 0; j < n; j++)
            {
                scanf("%d", &map[i][j]);
            }
        }
        sou(0);
        printf("%d\n", sum);
    }
    return 0;
}

 

UVA 11205 The broken pedometer

原文:http://www.cnblogs.com/zufezzt/p/4430910.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!