當前位置：首頁 > 人文社科 > 生活经验 >内容正文

生活经验

HDU-1459.非常可乐(BFS )

發布時間：2023/11/27 生活经验 28 豆豆

生活随笔收集整理的這篇文章主要介紹了 HDU-1459.非常可乐(BFS ) 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

　　這道題TLE了很多次，原來一直以為將數字化為最簡可以讓運算更快，但是去了簡化之后才發現，真正耗時的就是化簡....還和隊友學到了用狀態少直接數組模擬剛就能過...

　　本題大意：給出可樂的體積v1，給出兩個杯子v2和v3，要求v2 +?v3 ==?v1，每次只能從一個杯子倒到另一個杯子，問最少倒多少次可以將可樂平分。

　　思路：最后可樂肯定在可樂瓶和大杯子里面，直接BFS暴搜就行了。

　　參考代碼：

 1 #include <cstdio>
 2 #include <queue>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 struct node {
 7     int cur[3], step;
 8 } now, Next;
 9 
10 const int maxn = 100 + 5;
11 int v[3];
12 int  ans, t;
13 bool flag;
14 bool vis[maxn][maxn][maxn];
15 
16 void bfs() {
17     if(v[0] & 1) {
18         flag = false;
19         return;
20     } 
21     queue <node> Q;
22     now.cur[0] = v[0], now.cur[1] = 0, now.cur[2] = 0, now.step = 0;
23     vis[v[0]][0][0] = true;
24     Q.push(now);
25     while(!Q.empty()) {
26         now = Q.front();
27         Q.pop();
28         if(now.cur[0] == now.cur[1] && now.cur[2] == 0) {
29             ans = now.step;
30             return;
31         }
32         for(int i = 0; i < 3; i ++) {//i -> j
33             for(int j = 0; j < 3; j ++) {
34                 if(i != j) {
35                     Next = now;
36                     t = now.cur[i] + now.cur[j];
37                     if(t > v[j])  Next.cur[j] = v[j];
38                     else Next.cur[j] = t;
39                     Next.cur[i] = t - Next.cur[j];
40                     if(!vis[Next.cur[0]][Next.cur[1]][Next.cur[2]]) {
41                         Next.step = now.step + 1;
42                         Q.push(Next);
43                         vis[Next.cur[0]][Next.cur[1]][Next.cur[2]] = true;
44                     }
45                 }
46             }
47         }
48     }
49     flag = false;
50 }
51 
52 int main () {
53     while(~scanf("%d %d %d", &v[0], &v[1], &v[2])) {
54         memset(vis, false, sizeof(vis));
55         if(v[0] == 0 && v[1] == 0 && now.cur[2] == 0)  break;
56         flag = true, ans = 0;
57         if(v[1] < v[2]) {
58             t = v[1];
59             v[1] = v[2];
60             v[2] = t;
61         }
62         bfs();
63         if(flag) printf("%d\n", ans);
64         else    printf("NO\n");        
65     }
66     return 0;
67 }

View Code

?　　下面這個代碼的效率要高一點，區別在于倒水方式不同。

 1 #include <cstdio>
 2 #include <queue>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 struct node {
 7     int cur[3], step;
 8 } now, Next;
 9 
10 const int maxn = 100 + 5;
11 int v[3];
12 int  ans, t;
13 bool flag;
14 bool vis[maxn][maxn][maxn];
15 
16 void bfs() {
17     if(v[0] & 1) {
18         flag = false;
19         return;
20     } 
21     queue <node> Q;
22     now.cur[0] = v[0], now.cur[1] = 0, now.cur[2] = 0, now.step = 0;
23     vis[v[0]][0][0] = true;
24     Q.push(now);
25     while(!Q.empty()) {
26         now = Q.front();
27         Q.pop();
28         if(now.cur[0] == now.cur[1] && now.cur[2] == 0) {
29             ans = now.step;
30             return;
31         }
32         for(int i = 0; i < 3; i ++) {//i -> j
33             for(int j = 0; j < 3; j ++) {
34                 if(i != j) {
35                     Next = now;
36                     if(j == 0) {
37                         Next.cur[j] = now.cur[j] + now.cur[i];
38                         Next.cur[i] = 0;
39                     } else if(j == 1) {
40                         t = v[1] - now.cur[j];
41                         Next.cur[i] = now.cur[i] - t;
42                         Next.cur[i] = Next.cur[i] > 0 ? Next.cur[i] : 0;
43                         Next.cur[j] = now.cur[j] + now.cur[i];
44                         Next.cur[j] = Next.cur[j] < v[1] ? Next.cur[j] : v[1];
45                     } else {
46                         t = v[2] - now.cur[j];
47                         Next.cur[i] = now.cur[i] - t;
48                         Next.cur[i] = Next.cur[i] > 0 ? Next.cur[i] : 0;
49                         Next.cur[j] = now.cur[j] + now.cur[i];
50                         Next.cur[j] = Next.cur[j] < v[2] ? Next.cur[j] : v[2];
51                     }
52                     if(!vis[Next.cur[0]][Next.cur[1]][Next.cur[2]]) {
53                         Next.step = now.step + 1;
54                         Q.push(Next);
55                         vis[Next.cur[0]][Next.cur[1]][Next.cur[2]] = true;
56                     }
57                 }
58             }
59         }
60     }
61     flag = false;
62 }
63 
64 int main () {
65     while(~scanf("%d %d %d", &v[0], &v[1], &v[2])) {
66         memset(vis, false, sizeof(vis));
67         if(v[0] == 0 && v[1] == 0 && now.cur[2] == 0)  break;
68         flag = true, ans = 0;
69         if(v[1] < v[2]) {
70             t = v[1];
71             v[1] = v[2];
72             v[2] = t;
73         }
74         bfs();
75         if(flag) printf("%d\n", ans);
76         else    printf("NO\n");        
77     }
78     return 0;
79 }

View Code

轉載于:https://www.cnblogs.com/bianjunting/p/10493581.html

總結

以上是生活随笔為你收集整理的HDU-1459.非常可乐(BFS )的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。