酷酷的代码段

[C]​ 排日程 [第三届蓝桥杯决赛高职高专组-第五题]

【题目描述】

某保密单位机要人员 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

   

【代码段】

#include "stdio.h"

/* 满足要求则返回0； 否则返回1 */
int meetAC(int a, int c, int time[10][8])
{
    int i, ti = 0;
    for (i = 1; i < 8; ++i) ti+=(time[a][i] & time[c][i]);
    return ti>3?0:1;
}

/* 满足要求则返回0； 否则返回1 */
int meetABCD(int a, int b, int c, int d, int time[10][8])
{
    int i, check[8];
    for (i = 1; i < 8; ++i) 
        check[i] = time[a][i] + time[b][i] + time[c][i] + time[d][i];
    for (i = 1; i < 8; ++i) 
        if (check[i] < 2) return 1;
    return 0;
}

int meetAll(int a, int b, int c, int d, int e, int time[10][8])
{
    int i, check[8], ti = 0;;
    for (i = 1; i < 8; ++i) 
        check[i] = time[a][i] + time[b][i] + time[c][i] + time[d][i] + time[e][i];
    for (i = 1; i < 8; ++i) 
        if (check[i] == 5) ti++; 
    return ti>2?0:1;

}

int cout(int a, int b, int c, int d, int e, int time[10][8])
{
    int i;
    for (i = 1; i < 8; ++i) printf("%d", time[a][i]);
    printf("\n");
    for (i = 1; i < 8; ++i) printf("%d", time[b][i]);
    printf("\n");
    for (i = 1; i < 8; ++i) printf("%d", time[c][i]);
    printf("\n");
    for (i = 1; i < 8; ++i) printf("%d", time[d][i]);
    printf("\n");
    for (i = 1; i < 8; ++i) printf("%d", time[e][i]);
    printf("\n");
    return 0;
}

int main()
{
    int i, n; 
    int time[10][8];
    int a, b, c, d, e, flag = 0;
    
    /* 预处理一共7种可能的上班分配方案 */ 
    n = 1;
    for (a = 1; a < 8; a++){
        for (b = a+1; b < 8; b++) {
            if (b-a<3 || a+7-b<3) continue;
            for (i = 1; i < 8; ++i){
                if (i == a || i == b) time[n][i] = 0;else time[n][i] = 1;
            }
            n++; // n 为 8 (=7+1)
        }
    }

    for (a = 1; a < n; a++){
        if (!time[a][3]) continue;
        for (b = 1; b < n; b++){
            if (time[b][7]) continue;
            for (c = 1; c < n; c++){
                if(meetAC(a,c,time)) continue;
                for (d = 1; d < n; d++){
                    if (time[d][7]) continue;
                    if (meetABCD(a,b,c,d,time)) continue;
                    for (e = 1; e < n; e++){
                        if (!time[e][3]) continue;
                        if (time[e][7]) continue;
                        if(meetAll(a,b,c,d,e,time)) continue;
                        
                        //输出结果
                        if (flag) printf("\n");    else flag = 1; 
                        cout(a,b,c,d,e,time);
                    }
                }
            }
        }
    }
    return 0;
}

【运行结果】

0110111
1101110
0110111
1101110
1110110

0111011
1110110
0111011
1110110
1110110

1011011
1110110
1011011
1110110
1110110

1011101
1110110
1011101
1110110
1110110

--------------------------------
Process exited with return value 0
Press any key to continue . . .