某保密单位机要人员-解题报告

title: 某保密单位机要人员-解题报告
date: 2016-03-27 16:12:39
tags: 算法
categories: 算法

某保密单位机要人员 A，B，C，D，E 每周需要工作5天，休息2天。

上级要求每个人每周的工作日和休息日安排必须是固定的，不能在周间变更。

此外，由于工作需要，还有如下要求：

1. 所有人的连续工作日不能多于3天（注意：周日连到下周一也是连续）。

2. 一周中，至少有3天所有人都是上班的。

3. 任何一天，必须保证 A B C D 中至少有2人上班。

4. B D E 在周日那天必须休息。

5. A E 周三必须上班。

6. A C 一周中必须至少有4天能见面（即同时上班）。

你的任务是：编写程序，列出ABCDE所有可能的一周排班情况。工作日记为1，休息日记为0

A B C D E 每人占用1行记录，从星期一开始。

【输入、输出格式要求】

程序没有输入，要求输出所有可能的方案。

每个方案是7x5的矩阵。只有1和0组成。        

矩阵中的列表示星期几，从星期一开始。

矩阵的行分别表示A，B，C，D，E的作息时间表。

多个矩阵间用空行分隔开。

例如，如下的矩阵就是一个合格的解。请编程输出所有解(多个解的前后顺序不重要)。

0110111
1101110
0110111
1101110
1110110

【注意】

请仔细调试！您的程序只有能运行出正确结果的时候才有机会得分！

在评卷时使用的输入数据与试卷中给出的实例数据可能是不同的。

请把所有函数写在同一个文件中，调试好后，拷贝到【考生文件夹】下对应题号的“解答.txt”中即可。

相关的工程文件不要拷入。

源代码中不能使用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的API。

允许使用STL类库，但不能使用MFC或ATL等非ANSI c++标准的类库。

例如，不能使用CString类型（属于MFC类库），不能使用randomize, random函数（不属于ANSI C++标准）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int peo[30][7];
int temp[7];
int count = 0;
int judge()
{
    int min=100,max=0;
    for(int i=0;i<7;i++)
    {
        if(temp[i] == 0)
        {
            if(min>i)
                min = i;
            if(max<i)
                max = i;
        }
    }
    if((max-min)%6 == 3||(max-min)%6 == 4)
        return 1;
    else
        return 0;
}
int dfs(int depth)
{
    if(depth == 7)
    {
        int num = 0;
        for(int i=0;i<7;i++)
        {
            if(temp[i] == 1)
            {
                num++;
            }
        }
        if(num == 5)
        {
            
//          *peo[count] = *temp;
            if(judge())
            {
                memcpy(peo[count],temp,sizeof(temp));
                count++;
            }
            
        }
    }
    else
    {
        for(int i=0;i<2;i++)
        {
            temp[depth] = i;
            dfs(depth+1);
        }
    }
}
int fun(int i,int j,int k,int m,int n)
{
    int count = 0;
    for(int a=0;a<7;a++)
    {
        if(peo[i][a]+peo[j][a]+peo[k][a]+peo[m][a]+peo[n][a]==5)
        {
            count++;
        }
    }
    if(count>=3)
        return 1;
    else
        return 0;
}
int funa(int i,int j,int k,int m)
{
    int count = 0;
    for(int a=0;a<7;a++)
    {
        if(peo[i][a]+peo[j][a]+peo[k][a]+peo[m][a] >=2)
        {
            count++;
        }
    }
    if(count >= 7)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int funb(int i,int k)
{
    int count = 0;
    for(int a=0;a<7;a++)
    {
        if(peo[i][a]+peo[k][a] == 2)
        {
            count++;
        }
    }
    if(count>=4)
    {
        return 1;
    }
    else
        return 0;
}
void func(int i)
{
    for(int a=0;a<7;a++)
    {
        cout<<peo[i][a]<<" ";
    }
    cout<<endl;
}
int main()
{
    dfs(0);
    for(int i=0;i<count;i++)
    {
        for(int j=0;j<count;j++)
        {
            for(int k=0;k<count;k++)
            {
                for(int m=0;m<count;m++)
                {
                    for(int n=0;n<count;n++)
                    {
                        if(fun(i,j,k,m,n))
                        {
                            if(funa(i,j,k,m))
                            {
                                if(peo[j][6]+peo[m][6]+peo[n][6] == 0)
                                {
                                    if(peo[i][2] + peo[n][2] == 2)
                                    {
                                        if(funb(i,k))
                                        {
                                            func(i);
                                            func(j);
                                            func(k);
                                            func(m);
                                            func(n);
                                            //cout<<"================================================================="<<endl;
                                            cout<<endl;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}