蓝桥杯-分红酒

 1 #include <cstdio>
 2 #include <queue>
 3 #include <string.h>
 4 using namespace std;
 5 
 6 int full[4] = {9 , 7 , 4 , 2};
 7 typedef struct
 8 {
 9     int num[4];
10     int step;
11 }state;
12 
13 int vis[10][8][5][3];
14 int bfs(state &temp , int i , int j)//把i倒入j中
15 {
16     if(i == j) return 0;
17     if(temp.num[i] == 0) return 0;//如果i空，不用倒了
18     if(temp.num[j] == full[j]) return 0;//如果j满，不用倒了
19     if(temp.num[i] + temp.num[j] <=full[j])
20     {
21         temp.num[j] = temp.num[j] + temp.num[i];//把i全倒入j中，此时i空
22         temp.num[i] = 0;
23     }
24     else
25     {
26         temp.num[i] = temp.num[i] - (full[j] - temp.num[j]);//把i的一部分倒入j中，倒到j满
27         temp.num[j] = full[j];
28     }
29     if(vis[temp.num[0]][temp.num[1]][temp.num[2]][temp.num[3]]) return 0;//如果之前出现过这种情况，就不再反复倒了
30     vis[temp.num[0]][temp.num[1]][temp.num[2]][temp.num[3]] = 1;
31     temp.step++;
32     return 1;
33 }
34 int main()
35 {
36     state start , end;
37     start.num[0] = 9;
38     start.num[1] = 0;
39     start.num[2] = 0;
40     start.num[3] = 0;
41     start.step = 0;
42     while(scanf("%d%d%d%d",&end.num[0],&end.num[1],&end.num[2],&end.num[3])!=EOF)
43     {
44         memset(vis , 0 , sizeof(vis));
45         queue<state>q;
46         q.push(start);
47         if(end.num[0]>full[0] || end.num[1]>full[1] || end.num[2]>full[2] || end.num[3]>full[3])//给定的目标状态>瓶子容量
48         {
49             printf("-1\n");
50             continue;
51         }
52         if(end.num[0] + end.num[1] + end.num[2] + end.num[3] != 9)//一共分的是9升酒，输入不合法
53         {
54             printf("-1\n");
55             continue;
56         }
57         while(!q.empty())
58         {
59             state temp , temp1;
60             temp = q.front();
61             q.pop();
62             if(temp.num[0]==end.num[0] && temp.num[1]==end.num[1] && temp.num[2]==end.num[2] && temp.num[3]==end.num[3])
63             {
64                 printf("%d\n" , temp.step);
65                 break;
66             }
67             int i , j;
68             for(i = 0; i < 4; i++)//把i倒入j中
69             {
70                 for(j = 0; j < 4; j++)
71                 {
72                     temp1 = temp;
73                     if(bfs(temp1 , i , j))
74                     {
75                         q.push(temp1);
76                     }
77                 }
78             }
79         }
80     }
81     return 0;
82 }