题目分析:
对于A,B,C,D四支队伍,两两之间进行一场比赛,获胜得3分,平局得1分,失败不得分,现在对给出的四个队伍的得分,判断能否满足得到这种分数,且方案唯一输出yes,不唯一输出no,不可能则输出worng,由于一共只有6场比赛,直接通过暴力每一种可能,创建mat[i][j]存放队伍i和队伍j比赛对于i来说的得分,mat[j][i]存放对于j来说的得分,然后建立cal(int row,int col)深搜函数,对于每个mat[row][col]的结果都进行递归,查询得分为3,1,0的三种情况,然后再回溯,对于row和col下标到末尾是判断四支队伍的得分是否与输入相等,且需要注意的是mat[i][j]和mat[j][i]的得分是相对的(3对0,1对1用于最后删选去掉不可能的情况)
代码:
1 #include<iostream> 2 #include<string.h> 3 using namespace std; 4 5 int A, B, C, D; 6 int mat[5][5]; 7 int ans; 8 9 bool judge(){ 10 int score[5]; 11 memset(score, 0, sizeof(score)); 12 for(int i = 1; i <= 4; i++){ 13 for(int j = 1; j <= 4; j++){ 14 if(i != j){ 15 score[i]+=mat[i][j]; 16 if(mat[i][j] == 3 && mat[j][i] != 0) return false; 17 if(mat[i][j] == 0 && mat[j][i] != 3) return false; 18 if(mat[i][j] == 1 && mat[j][i] != 1) return false; 19 } 20 } 21 } 22 if(score[1] == A && score[2] == B && score[3] == C && score[4] == D){ 23 return true; 24 } 25 else return false; 26 } 27 28 void cal(int row, int col){ 29 if(col == 5){ 30 cal(row+1, 1); 31 return; 32 } 33 if(row == 5){ 34 if(judge()) ans++; 35 return; 36 } 37 38 if(row != col){ 39 mat[row][col] = 3; 40 cal(row, col+1); 41 42 mat[row][col] = 1; 43 cal(row, col+1); 44 45 mat[row][col] = 0; 46 cal(row, col+1); 47 }else{ 48 cal(row, col+1); 49 } 50 } 51 52 int main(){ 53 int t; 54 scanf("%d", &t); 55 int cnt = 1; 56 while(t--){ 57 scanf("%d%d%d%d", &A, &B, &C, &D); 58 memset(mat, 0, sizeof(mat)); 59 ans = 0; 60 cal(1, 1); 61 if(ans == 0) printf("Case #%d: Wrong Scoreboard\n", cnt++); 62 else if(ans == 1) printf("Case #%d: Yes\n", cnt++); 63 else printf("Case #%d: No\n", cnt++); 64 } 65 return 0; 66 }