The 2016 ACM-ICPC Asia China-Final L World Cup(深搜+回溯 暴力求解)

 

题目分析:

对于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
", cnt++);
62         else if(ans == 1) printf("Case #%d: Yes
", cnt++);
63         else printf("Case #%d: No
", cnt++);    
64     }    
65     return 0;
66 }
原文地址:https://www.cnblogs.com/findview/p/11798220.html