首页 > 代码库 > HDU 1495 非常可乐 BFS 搜索
HDU 1495 非常可乐 BFS 搜索
http://acm.hdu.edu.cn/showproblem.php?pid=1495
题目就不说了， 说说思路！
倒可乐 无非有6种情况:
1. S 向 M 倒
2. S 向 N 倒
3. N 向 M 倒
4. N 向 S 倒
5. M 向 S 倒
6. M 向 N 倒
根据上述的六种情况来进行模拟， 每次模拟的结果都放进队列里面。
注意： 还要用到标记数组，防止数据重复进入队列导致爆栈。
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<math.h> 4 #include<queue> 5 #include<string.h> 6 #include<iostream> 7 using namespace std; 8 #define maxn 110 9 10 struct Node 11 { 12 int m;//M瓶子中装的可乐数m 13 int n; 14 int s; 15 int k;//总共倒的次数 16 }; 17 int M, N, S; 18 int BFS(Node P); 19 bool vis[maxn][maxn][maxn];//标记此情况是否有过, 防止重复 20 int main() 21 { 22 Node P; 23 while(scanf("%d%d%d",&S,&M,&N),M+N+S) 24 { 25 int t; 26 if(M < N)//将M存为最大的 27 t = M, M = N, N = t; 28 memset(vis,0,sizeof(vis)); 29 P.s = S, P.m = P.n = P.k = 0; 30 int ans = -1; 31 if(S%2 == 0)//奇数是没法平分的 32 ans = BFS(P); 33 34 if(ans == -1) 35 printf("NO\n"); 36 else 37 printf("%d\n",ans); 38 } 39 return 0; 40 } 41 42 int BFS(Node P) 43 { 44 queue<Node> Q; 45 Q.push(P); 46 int x; 47 while( !Q.empty() ) 48 { 49 Node Pn; 50 Pn = Q.front(); 51 Q.pop(); 52 53 if(Pn.s == S/2 && Pn.m == S/2 )//当两个瓶子都是S/2则满足 54 return Pn.k; 55 56 P.k = Pn.k + 1; 57 /*下面就是倒可乐的过程*/ 58 if(Pn.s < S) 59 { 60 x = S - Pn.s; 61 62 if(Pn.n > x && !vis[S][Pn.n-x][Pn.m]) 63 { 64 vis[S][Pn.n-x][Pn.m] = 1; 65 P.s = S, P.m = Pn.m, P.n = Pn.n-x; 66 Q.push(P); 67 } 68 else if(Pn.n <= x && !vis[Pn.s+Pn.n][0][Pn.m]) 69 { 70 vis[Pn.s+Pn.n][0][Pn.m] = 1; 71 P.s = Pn.s + Pn.n, P.m = Pn.m, P.n = 0; 72 Q.push(P); 73 } 74 75 if(Pn.m > x && !vis[S][Pn.n][Pn.m-x]) 76 { 77 vis[S][Pn.n][Pn.m-x] = 1; 78 P.s = S, P.n = Pn.n, P.m = Pn.m-x; 79 Q.push(P); 80 } 81 else if(Pn.m <= x && !vis[Pn.s+Pn.m][Pn.n][0]) 82 { 83 vis[Pn.s+Pn.m][Pn.n][0] = 1; 84 P.s = Pn.s+Pn.m, P.n = Pn.n, P.m = 0; 85 Q.push(P); 86 } 87 } 88 89 if(Pn.n < N) 90 { 91 x = N - Pn.n; 92 93 if(Pn.s > x && !vis[Pn.s-x][N][Pn.m]) 94 { 95 vis[Pn.s-x][N][Pn.m] = 1; 96 P.s = Pn.s-x, P.n = N, P.m = Pn.m; 97 Q.push(P); 98 } 99 else if(Pn.s <= x && !vis[0][Pn.n+Pn.s][Pn.m])100 {101 vis[0][Pn.n+Pn.s][Pn.m] = 1;102 P.s = 0, P.n = Pn.n+Pn.s, P.m = Pn.m;103 Q.push(P);104 }105 106 if(Pn.m > x && !vis[Pn.s][N][Pn.m-x])107 {108 vis[Pn.s][N][Pn.m-x] = 1;109 P.s = Pn.s, P.n = N, P.m = Pn.m-x;110 Q.push(P);111 }112 else if(Pn.m <= x && !vis[Pn.s][Pn.n+Pn.m][0])113 {114 vis[Pn.s][Pn.n+Pn.m][0] = 1;115 P.s = Pn.s, P.n = Pn.n+Pn.m, P.m = 0;116 Q.push(P);117 }118 }119 120 if(Pn.m < M)121 {122 x = M - Pn.m;123 124 if(Pn.s > x && !vis[Pn.s-x][Pn.n][M])125 {126 vis[Pn.s-x][Pn.n][M] = 1;127 P.s = Pn.s-x, P.n = Pn.n, P.m = M;128 Q.push(P);129 }130 else if(Pn.s <= x && !vis[0][Pn.n][Pn.m+Pn.s])131 {132 vis[0][Pn.n][Pn.m+Pn.s] = 1;133 P.s = 0, P.n = Pn.n, P.m = Pn.m+Pn.s;134 Q.push(P);135 }136 137 if(Pn.n > x && !vis[Pn.s][Pn.n-x][M])138 {139 vis[Pn.s][Pn.n-x][M] = 1;140 P.s = Pn.s, P.n = Pn.n-x, P.m = M;141 Q.push(P);142 }143 else if(Pn.n <= x && !vis[Pn.s][0][Pn.m+Pn.n])144 {145 vis[Pn.s][0][Pn.m+Pn.n] = 1;146 P.s = Pn.s-x, P.n =0, P.m = Pn.m+Pn.n;147 Q.push(P);148 }149 }150 }151 return -1;152 }
HDU 1495 非常可乐 BFS 搜索
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。